[Java] SinglyLinkedList 구현

LinkedList란?

LinkedList는 배열과 달리 데이터를 저장하는 선형 자료구조입니다. 각 요소(노드)는 데이터와 다음 노드를 가리키는 포인터(주소)를 포함하고 있으며, 자바의 LinkedList는 이중 연결 리스트(doubly linked list)로 구현되어 각 노드가 이전 노드와 다음 노드의 주소를 모두 저장합니다.

노드들은 동적으로 메모리가 할당되며, 연속적인 메모리 주소를 가지지 않습니다.

 

LinkedList의 특징

1. 동적 크기 조절
   LinkedList는 배열과 달리 크기를 미리 지정할 필요가 없습니다. 노드가 추가되거나 삭제될 때 메모리를 동적으로 할당하거나 해제합니다.
2. 순차적 접근
   각 노드는 연결된 다음 노드의 주소를 통해 접근하기 때문에, 특정 위치의 데이터를 찾으려면 시작 노드부터 순차적으로 탐색해야 합니다. 따라서 접근 시간 복잡도는 O(n)입니다.

 

장점

1. 동적인 크기 조절
   배열과 달리 크기가 고정되어 있지 않으므로 요소를 추가하거나 삭제할 때 새로운 배열을 생성하지 않아도 됩니다.
2. 삽입/삭제 효율
   특정 위치에서 데이터를 추가하거나 삭제할 때, 포인터만 변경하면 되므로 빠르게 처리할 수 있습니다. (시간 복잡도 O(1), 특정 위치 탐색 시간 제외)

단점

1. 접근 시간
   배열은 인덱스를 기반으로 데이터에 접근할 수 있어 시간 복잡도가 O(1)이지만, LinkedList는 순차적으로 노드를 탐색해야 하므로 시간 복잡도는 O(n)입니다.
2. 추가 메모리 사용
   각 노드가 데이터 외에도 이전 노드와 다음 노드를 가리키는 포인터를 저장해야 하므로, 배열보다 더 많은 메모리를 사용합니다.

 

 

 

LinkedList를 사용하는 경우

• 배열의 가장 큰 단점은 크기가 고정되어 있다는 점입니다. 크기를 변경하려면 새로운 배열을 생성하고 데이터를 복사해야 하는 번거로움이 있습니다.
• LinkedList는 크기가 유동적으로 변경될 가능성이 있거나, 삽입/삭제 연산이 빈번하게 발생할 경우 적합합니다.
  예: 데이터의 삽입/삭제가 많고, 탐색보다 리스트를 재구성하는 작업이 우선인 경우.

LinkedList와 배열의 비교

특징	배열	LinkedList
메모리 구조	연속된 메모리	노드로 분산된 메모리
접근 시간	O(1) (인덱스 기반)	O(n) (순차 탐색)
삽입/삭제	느림 (요소 이동 필요)	빠름 (포인터 조정)
메모리 사용	효율적	추가 메모리 소요

LinkedList는 상황에 따라 배열보다 유연하고 효율적인 선택이 될 수 있습니다.

 

 

LinkedList 종류

 

• Singly Linked List (단일 연결 리스트)
  각 노드가 데이터와 다음 노드의 주소(포인터)만을 저장합니다.
  데이터 삽입과 삭제가 간단하며 메모리 사용이 적습니다. 하지만 뒤로만 이동할 수 있고, 이전 노드로 돌아갈 수 없다는 단점이 있습니다.
• Doubly Linked List (이중 연결 리스트)
  각 노드가 데이터, 이전 노드의 주소, 다음 노드의 주소를 저장합니다.
  양방향으로 탐색이 가능해 효율적이지만, 포인터를 추가로 저장해야 하므로 메모리 사용량이 증가합니다.
• Circular Linked List (원형 연결 리스트)
  마지막 노드가 첫 번째 노드를 가리키도록 연결된 형태입니다.
  Singly Linked List나 Doubly Linked List에서 원형 구조를 추가한 형태로, 리스트의 끝에서 다시 처음으로 순환할 수 있습니다.

 

 

SinglyLinkedList 구현

Link 인터페이스

public interface ListIfs<T> {

    // 가장 뒤에 요소를 추가
    public void add(T element);

    // 해당 index에 요소 추가
    public void insert(int index, T element);

    // index 에 있는 요소를 가지고 오기
    public T get(int idx);

    // index 에 있는 요소 제거
    public void remove(int index);

    // 해당 요소를 제거
    public void remove(T element);

    // 모든 요소 삭제
    public void removeAll();

    // 해당 리스트의 사이즈
    public int size();

    // 비어있는지
    public boolean isEmpty();

    // 모든 요소 출력
    public void printAll();

}

 

 

Singly Linked List 구현

// Node 클래스: 데이터를 저장하고 다음 노드의 주소를 저장하는 역할
class Node<T> {
    Node<T> link; // 다음 노드를 가리키는 참조 변수
    T data;       // 현재 노드의 데이터

    public Node(T data) {
        this.data = data;
    }
}

// SinglyLinkedList 클래스: 단일 연결 리스트 구현
public class SinglyLinkedList<T> implements ListIfs<T> {
    private int size; // 리스트의 크기를 저장하는 변수

    // 시작 노드를 저장하는 변수 (리스트의 첫 번째 노드)
    private Node<T> startNode;

    // 생성자: 리스트 초기화
    public SinglyLinkedList() {
        size = 0;
        startNode = null;
    }

    // 맨 뒤에 요소 추가하기
    @Override
    public void add(T element) {
        Node<T> newNode = new Node<>(element); // 새로운 노드 생성
        size++;

        // 리스트가 비어 있으면 새로운 노드를 시작 노드로 설정
        if (startNode == null) {
            startNode = newNode;
            return;
        }

        // 마지막 노드까지 이동
        Node<T> curNode = startNode;
        while (curNode.link != null) {
            curNode = curNode.link;
        }

        // 마지막 노드의 링크를 새로운 노드로 설정
        curNode.link = newNode;
    }

    // 특정 인덱스에 요소 삽입하기
    @Override
    public void insert(int index, T element) {
        if (index > size) { // 유효하지 않은 인덱스일 경우 예외 발생
            throw new ArrayIndexOutOfBoundsException("크기 초과");
        }

        Node<T> newNode = new Node<>(element);
        size++; // 리스트 크기 증가

        // 시작 위치에 삽입하는 경우
        if (index == 0) {
            newNode.link = startNode;
            startNode = newNode;
            return;
        }

        // 삽입 위치 이전 노드까지 이동
        Node<T> curNode = startNode;
        for (int i = 1; i < index; i++) {
            curNode = curNode.link;
        }

        // 새로운 노드를 삽입 위치에 연결
        newNode.link = curNode.link;
        curNode.link = newNode;
    }

    // 특정 인덱스의 요소 가져오기
    @Override
    public T get(int index) {
        if (index >= size) { // 유효하지 않은 인덱스일 경우 예외 발생
            throw new ArrayIndexOutOfBoundsException();
        }

        Node<T> curNode = startNode;
        for (int i = 0; i < index; i++) {
            curNode = curNode.link;
        }

        return curNode.data; // 해당 노드의 데이터 반환
    }

    // 특정 인덱스의 요소 삭제하기
    @Override
    public void remove(int index) {
        if (index >= size) { // 유효하지 않은 인덱스일 경우 예외 발생
            throw new ArrayIndexOutOfBoundsException();
        }

        size--; // 리스트 크기 감소

        // 첫 번째 요소를 삭제하는 경우
        if (index == 0) {
            startNode = startNode.link;
            return;
        }

        // 삭제할 요소 이전 노드까지 이동
        Node<T> curNode = startNode;
        for (int i = 1; i < index; i++) {
            curNode = curNode.link;
        }

        // 링크를 조정하여 노드를 삭제
        curNode.link = curNode.link.link;
    }

    // 특정 요소를 삭제하기
    @Override
    public void remove(T element) {
        if (startNode == null) { // 리스트가 비어 있는 경우
            return;
        }

        // 첫 번째 요소가 삭제 대상인 경우
        if (startNode.data.equals(element)) {
            startNode = startNode.link;
            size--;
            return;
        }

        // 삭제 대상 요소를 탐색하며 링크 조정
        Node<T> curNode = startNode;
        while (curNode.link != null) {
            if (curNode.link.data.equals(element)) {
                curNode.link = curNode.link.link;
                size--;
                return;
            }
            curNode = curNode.link;
        }
    }

    // 모든 요소 삭제하기
    @Override
    public void removeAll() {
        startNode = null; // 시작 노드를 null로 설정하여 리스트 초기화
        size = 0;
    }

    // 리스트의 크기 반환
    @Override
    public int size() {
        return this.size;
    }

    // 리스트가 비어 있는지 확인
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 리스트의 모든 요소 출력하기
    @Override
    public void printAll() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");

        Node<T> curNode = startNode;
        while (curNode != null) {
            sb.append(curNode.data).append(", ");
            curNode = curNode.link;
        }

        // 마지막 요소 이후의 콤마 제거
        if (sb.length() > 1) {
            sb.setLength(sb.length() - 2);
        }

        sb.append("]");
        System.out.println(sb);
    }
}