[자료 구조] 연결 리스트

연결 리스트란?

데이터를 노드(Node)라는 객체로 구성하여 저장하는 자료구조

각각의 노드는 데이터 필드와 다음 노드를 가리키는 포인터(주소)필드로 구성되어 있음

포인터를 이용하여 각 노드들이 서로 연결되어 있기 때문에 연결 리스트라는 이름이 붙음

연결리스트의 장점

1. 동적 메모리 할당과 크기 조정이 가능

   필요한 만큼 노드를 동적으로 할당하여 사용하기 때문에 메모리를 효율적으로 사용 가능. 또한, 노드 삭제/추가를 함으로써 리스트의 크기를 동적으로 조정 가능

2. 삽입과 삭제 용이

   연결 리스트에서는 노드를 추가하거나 삭제하기 위해 해당 노드의 포인터를 수정하는 작업만 필요.

   → 반면 배열에서는 데이터를 삭제/삽입때마다 다른 요소를 이동해야 하기 때문에 시간이 오래걸림

3. 메모리 공간을 미리 예약할 필요가 없음

   노드를 추가할 때마다 새로운 메모리를 동적으로 할당하기 때문에 메모리 공간을 미리 예약할 필요가 없음

4. 순서를 유지 하지 않아도 됨

   데이터 삽입과 삭제가 노드의 포인터를 수정하는 작업으로 이루어지기때문에 순서를 유지할 필요가 없음

5. 중간 데이터에 대한 접근이 빠름

   노드의 포인터를 이용하여 각 노드들이 연결되어 있기 때문에 중간 데이터에 대한 접근이 빠름

연결리스트의 단점

1. 임의 접근이 불가능함

   각 노드들이 포인터로 연결되어 있기 때문에 특정 인덱스를 가지고 데이터에 접근하는 것이 불가능

   따라서, 특정 인덱스의 데이터를 검색하려면 처음부터 순차적으로 탐색해야함

2. 순차적인 접근이 필요한 경우 성능 저하

   임의 접근이 불가능하기 때문에, 데이터를 순차적으로 접근해야함. 이 때문에, 데이터를 빠르게 접근하거나 수정하는 것이 배열보다 느릴 수 있음

3. 추가적인 포인터 메모리를 필요로 함

   각 노드들이 다음 노드를 가리키는 포인터를 가지고 있기 때문에, 추가적인 메모리를 사용해야함.

연결리스트와 배열의 차이

1. 메모리 할당 방식
   • 배열 : 연속된 메모리 공간에 데이터를 저장.
   • 연결 리스트 : 각 노드가 다음 노드를 가리키를 포인터를 리용하여 연결되어 있는 형태로 메모리 할당.
2. 크기 조정 방식
   • 배열 : 크기를 미리 지정해야함. 크기 변경시 새로운 배열을 할당하고 기존 배열을 복사해야함
   • 연결 리스트 : 필요한 만큼 노드를 동적으로 할당하여 사용하기 때문에 동적으로 조정 가능
3. 접근 방식
   • 배열 : 인덱스를 이용하여 특정 위치에 데이터에 바로 접근할 수 있음
   • 연결 리스트 : 포인터를 이용하여 다음 노드를 참조해야 하므로 특정 위치의 데이터에 접근하기 위해서는 처음부터 순차적으로 탐색 필요
4. 삽입, 삭제 성능
   • 배열 : 데이터를 삽입하거나 삭제할때마다 해당 위치 이후의 모든 요소들을 이동시켜야함
   • 연결 리스트 : 해당 노드의 포인터만 수정하면 되므로 삽입/삭제가 빠름
5. 메모리 사용량
   • 배열 : 미리 할당된 메모리 공간에 데이터를 저장하기 때문에 메모리 사용량이 고정적임
   • 연결 리스트 : 필요한 만큼 노드를 동적으로 할당하기 때문에 메모리 사용량이 더욱 유연함

⇒ 배열은 데이터를 빠르게 접근할 수 있고 크기가 고정적일 때 유용. 반면에 연결 리스트는 크기가 동적으로 변화하거나 데이터의 삽입, 삭제가 빈번히 일어날 때 유용.

연결 리스트의 종류

• 단일 연결 리스트(Singly Linked List)
  • 각 노드가 다음 노드를 가리키는 포인터만 가지고 있음
• 이중 연결 리스트(Doubly Linked List)
  • 각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터를 가지고 있음
• 원형 연결 리스트(Circular Linked List)
  • 마지막 노드가 첫 번째 노드를 가리키도록 연결된 리스트

연결 리스트 코드

public class LinkedList {
    private Node head; // 연결 리스트의 시작 노드를 가리키는 변수

    // 노드를 표현하는 클래스
    private class Node {
        int data; // 데이터를 저장하는 변수
        Node next; // 다음 노드를 가리키는 변수
    }

    // 연결 리스트에 데이터를 삽입하는 메소드
    public void insert(int data) {
        Node newNode = new Node(); // 새로운 노드 생성
        newNode.data = data; // 데이터 저장

        // 연결 리스트가 비어있는 경우
        if (head == null) {
            head = newNode; // 새로운 노드를 시작 노드로 지정
        } 
        // 연결 리스트가 비어있지 않은 경우
        else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // 마지막 노드까지 이동
            }
            current.next = newNode; // 마지막 노드 다음에 새로운 노드를 추가
        }
    }

    // 연결 리스트를 출력하는 메소드
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.printList(); // 1 2 3 출력
    }
}

참고
https://code-lab1.tistory.com/2
https://www.w3schools.com/java/java_linkedlist.asp