[자료구조] 연결 리스트(LinkedList) 자료구조 알아보기 & Java 예제 코드

자료구조 중 연결 리스트(Linked List)의 개념과 Java 예제 코드를 정리해보자.

 

---

 

연결 리스트(Linked List)란?

LinkedList는 자료구조 중 하나로 데이터 요소를 연결된 노드로 표현하는 방식이다.

각 노드는 데이터와 다음 노드를 가리키는 포인터(또는 링크)로 구성된다.

이 포인터를 통해 다음 노드로 이동하면서 데이터를 순차적으로 접근할 수 있다.

LinkedList는 동적으로 크기가 조절될 수 있으며, 데이터의 삽입과 삭제가 빠르게 이루어진다는 특징이 있다.

 

LinkedList의 기본 개념을 정리해보면 다음과 같다.

 

1. 노드(Node) : LinkedList의 기본 구성 요소로, 데이터와 다음 노드를 가리키는 링크(포인터)로 구성된다.
2. 헤드(Head) : LinkedList의 첫 번째 노드를 가리키는 포인터입니다. LinkedList에서 데이터에 접근하기 위해서는 헤드부터 시작해야 한다.
3. 데이터(Data) : 각 노드가 저장하는 실제 값 또는 객체이다.
4. 링크(포인터/Pointer) : 노드들을 연결하는 역할을 한다. 각 노드는 다음 노드를 가리키는 링크를 가지고 있다.

출처 :  https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/

 

 

연결 리스트(Linked List)의 장점 및 단점

장점

1. 빠른 삽입과 삭제 : LinkedList는 각 노드가 다음 노드를 가리키는 링크를 가지고 있기 때문에 삽입과 삭제 연산이 노드의 재배치 없이 수행될 수 있다. 따라서 배열과 달리 데이터의 이동이 필요 없으므로 시간 복잡도가 O(1)에 가깝다. 링크를 이용해 노드들을 연결하기 때문에 중간 위치에 노드를 삽입하거나 삭제하는 작업 또한 배열보다 훨씬 효율적이며, 중간 위치에 대한 포인터 조정만으로 해당 작업을 수행할 수 있다.
2. 용이한 동적 크기 조절 : LinkedList는 노드의 동적인 삽입과 삭제가 가능하므로, 크기를 실시간으로 조절할 수 있다. 데이터의 추가 또는 삭제에 따라 메모리를 유연하게 할당하고 해제할 수 있어서 메모리를 효율적으로 관리할 수 있다.

 

단점

1. 임의 접근이 어렵다 : LinkedList는 데이터에 순차적으로 접근하는 것이 효율적이다. 따라서 특정 위치의 데이터에 접근하려면 처음(Head)부터 순차적으로 탐색해야 한다. 이로 인해 임의 접근이 필요한 작업(예: 인덱스로 특정 요소에 접근)은 성능이 떨어질 수 있다. 배열은 인덱스를 이용해 O(1)의 시간 복잡도로 임의 접근이 가능한 반면, LinkedList는 O(n)의 시간 복잡도가 소요된다.
2. 추가적인 메모리 공간이 필요 : LinkedList는 각 노드마다 다음 노드를 가리키는 포인터를 유지해야 한다. 따라서 배열에 비해 추가적인 메모리 공간이 필요하며, 이로 인해 메모리 사용량이 더 많을 수 있다.
3. 검색 시간이 길다 : LinkedList는 데이터를 순차적으로 접근해야 하므로 특정 요소를 찾기 위해서는 처음부터 시작하여 찾고자 하는 요소를 찾을 때까지 노드를 순차적으로 탐색해야 한다. 따라서 검색 작업은 배열에 비해 성능이 떨어질 수 있다.

 

정리해보면 LinkedList는 삽입과 삭제가 빠르며 동적 크기 조절이 용이하다는 장점을 가지고 있지만, 임의 접근과 검색에 대해서는 성능이 좋지 않다는 단점이 있다.

따라서 데이터의 삽입과 삭제가 빈번하게 발생하고, 임의 접근이 필요하지 않은 상황에서 LinkedList를 사용하는 것이 적합합니다.

 

 

LinkedList 예시 코드(Java)

class Node {
    int data; // 데이터를 저장하는 변수
    Node next; // 다음 노드를 가리키는 링크(포인터)

    public Node(int data) {
        this.data = data;
        this.next = null; // 초기에는 다음 노드를 가리키는 링크가 없으므로 null로 설정
    }
}

class LinkedList {
    Node head; // 첫 번째 노드를 가리키는 헤드(포인터)

    public LinkedList() {
        this.head = null; // 초기에는 헤드가 null인 빈 LinkedList
    }

    // 노드를 LinkedList의 맨 끝에 추가하는 메서드
    public void append(int data) {
        Node newNode = new Node(data); // 새로운 노드 생성

        if (head == null) {
            // LinkedList가 비어있는 경우, 헤드로 설정
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // 마지막 노드까지 이동
            }
            current.next = newNode; // 마지막 노드의 다음 링크에 새로운 노드를 연결
        }
    }

    // LinkedList의 모든 요소를 출력하는 메서드
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " "); // 현재 노드의 데이터 출력
            current = current.next; // 다음 노드로 이동
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList(); // LinkedList 인스턴스 생성

        list.append(1); // LinkedList에 1을 추가
        list.append(2); // LinkedList에 2를 추가
        list.append(3); // LinkedList에 3을 추가

        list.display(); // LinkedList의 모든 요소를 출력 (1 2 3)
    }
}

 

이 예시에서는 LinkedList 클래스와 Node 클래스를 정의하고, LinkedList의 기본적인 동작을 구현했다.

append 메서드를 사용하여 LinkedList의 맨 끝에 새로운 노드를 추가하고, display 메서드를 사용하여 LinkedList의 모든 요소를 출력했다.