LinkedList

• 연결리스트는 데이터 요소가 순서대로 연결된 데이터 구조이다.
• 각 요소는 자신의 데이터와 다음 요소를 가리키는 포인터(참조)로 이루어져 있다.
• 이러한 구조로 배열과 달리 연결리스트는 각 요소의 위치가 연속적이지 않을 수 있다.

Singly Linked List (단일 연결 리스트)

각 요소가 데이터와 다음 요소를 가리키는 포인터로 이루어져 있다.

맨 끝 요소는 다음 요소를 가리키는 포인터가 null이다.

Doubly Linked List (이중 연결 리스트)

각 요소가 데이터와 이전 요소를 가리키는 포인터, 다음 요소를 가리키는 포인터로 이루어져 있다.

양방향으로 순회가 가능하다.

 

[단일 연결 리스트 Code]

public class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }

    // 요소 추가
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 요소 출럭
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.add(10);
        list.add(20);
        list.add(30);

        list.display();
    }
}

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

 

장점

• 동적으로 크기를 조절할 수 있어 동적 메모리 할당이 가능하다. 런타임에 메모리를 할당하고 해제할 수 있다.
  
  • Array의 경우, 데이터를 삽입하여 모든 공간이 꽉 차게 되면 새로운 메모리 공간을 할당받아 옮겨야 하지만,
    LinkedList는 추가할 때마다 동적으로 메모리 공간을 할당받는다.
• 특정 위치에 요소를 추가하거나 삭제하는 연산이 효율적이다.
  • 중간 삽입 없이 맨 앞과 맨 뒤에만 삽입한다면 O(1)의 시간 복잡도를 가진다.

단점

• 특정 위치의 요소에 접근하려면 처음부터 순차적으로 찾아가야 한다.
  • 특정 인덱스에 빠르게 접근하는 것이 배열보다 느리다.
  • 만약 중간 삽입을 하게 되면 삽입할 위치를 찾고 삽입 연산을 진행하는데, 이때 O(n)의 시간 복잡도를 가진다.
• 각 요소에 데이터와 링크를 위한 추가적인 메모리가 필요하다.
  • 연결 리스트는 각 노드를 따라가야 하므로 메모리 사용이 더 많을 수 있다.

연결 리스트는 삽입과 삭제가 빈번한 상황에서 효율적으로 사용된다.