[DS] Linked List(링크드 리스트)란? + 자바 구현 예시

링크드 리스트란 말만 놓고 보면 연결된 리스트라고 해석된다. 그러나 왜 연결된 리스트라고 이름 붙었는지, 뭐가 연결돼있는 건지는 알 수 없다. 링크드 리스트는 뭘까?

네이버 사전에 검색해봤는데 의외로 뜻이 있어서 가져왔다.

 

각 항목이 데이터와 그 인접 항목의 포인터를 갖고 있는 리스트

 

데이터와 항목은 무슨 차이가 있는 건가? 포인터는 뭔가? 인접 항목은 정확히 뭘 말하는 건가? 의문투성이다.

위키백과에서 말하는 링크드 리스트는 아래와 같다.

 

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결 리스트 - 위키백과, 우리 모두의 백과사전

연결 리스트, 링크드 리스트는 각 노드가 데이터와 포인터를 갖고 한 줄로 연결돼 있는 방식으로 데이터를 저장하는 자료구조다. 이름에서 말하듯 데이터를 담고 있는 노드들이 연결돼 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당한다. 연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트 등이 있다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가, 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열, 트리 구조와 달리 특정 위치의 데이터를 검색하는 데는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

https://en.wikipedia.org/wiki/Linked_list

Linked list - Wikipedia

연결 리스트는 메모리의 물리적 배치에 따라 순서가 지정되지 않는 데이터 요소의 선형 모음이다. 대신 각 요소는 다음 요소를 가리킨다. 연결 리스트는 시퀀스를 함께 나타내는 노드 모음으로 구성된 자료구조다. 가장 기본적인 형태로 각 노드는 데이터, 시퀀스의 다음 노드에 대한 참조(=링크)를 포함한다. 이 구조를 쓰면 반복하는 동안 시퀀스의 모든 위치에서 요소를 효율적으로 삽입하거나 제거할 수 있다. 더 복잡한 변형은 링크를 추가해 임의의 위치에 노드를 더 효율적으로 삽입, 제거할 수 있다. 연결 리스트의 단점은 접근 시간이 선형적이고 파이프라인으로 전송하기 어렵단 것이다. 랜덤 액세스와 같은 빠른 접근은 불가능하다. 배열은 연결 리스트에 비해 캐시 인접성이 높다
연결 리스트는 가장 단순하고 일반적인 자료구조 중 하나다. 리스트, 스택, 큐, 연관 배열, S-표현을 포함한 여러 일반적인 추상 데이터 유형을 구현하는 데 사용할 수 있지만, 연결 리스트를 기반으로 쓰지 않고 직접 이런 자료구조를 표현할 수 있다
기존 배열에 비해 연결 리스트의 장점은 데이터 항목을 메모리나 디스크에 연속으로 저장할 필요가 없기 때문에, 전체 구조를 재할당하거나 재구성할 필요 없이 리스트 요소를 쉽게 삽입하거나 제거할 수 있다. 반면 런타임에 배열을 재구성하는 건 훨씬 비용이 많이 든다. 연결 리스트는 리스트의 어느 지점에서나 노드를 삽입, 제거할 수 있으며 리스트 트래버설 동안 링크가 메모리에 추가, 제거되기 전에 링크를 유지함으로써 일정 수의 작업을 수행할 수 있다
그러나 간단한 연결 리스트 자체로는 데이터에 대한 랜덤 액세스나 효율적 인덱싱을 허용하지 않기 때문에 리스트의 마지막 요소를 얻거나 주어진 데이터를 포함하는 노드를 찾거나, 새 노드를 삽입하는 것과 같은 많은 기본 작업은 대부분 또는 전부 반복해야 할 수 있다

 

정리하면 링크드 리스트는 다음 요소를 가리키는 요소(노드)들로 구성된 리스트라는 뜻이다. 다음 요소를 가리킬 때 요소들이 가진 포인터라는 걸 사용한다. 장단점은 대충 저런 듯하다.

위키백과의 설명만으론 조금 부족해 보여서 다른 사람들은 어떻게 설명하는지 확인해봤다.

 

https://hwan1001.tistory.com/5

[JAVA] 자료구조 클래스 - LinkedList(연결리스트)

링크드 리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결돼 있는 방식으로 데이터를 저장하는 자료구조다. 이름처럼 데이터를 담고 있는 노드들이 연결돼 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다. 늘어선 노드의 중간지점에서도 자료 추가, 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열, 트리 구조와 달리 특정 위치의 데이터를 검색할 때는 O(n)의 시간이 걸린단 단점이 있다.

 

https://www.geeksforgeeks.org/linked-list-in-java/

LinkedList in Java - GeeksforGeeks

링크드 리스트는 java.util 패키지에 있는 컬렉션 프레임워크의 일부다. 이 클래스는 요소가 연속된 위치에 저장되지 않고 모든 요소가 데이터, 주소 부분이 있는 별도의 객체인 선형 데이터 구조인 링크드리스트 자료구조의 구현이다. 요소는 포인터와 주소를 사용해 연결된다. 각 요소를 노드라고 한다. 삽입, 삭제의 역동성과 용이성으로 인해 배열보다 선호된다. 또한 노드에 직접 접근할 수 없다는 단점이 있다. 대신 head에서 시작해 링크를 따라 접근하려는 노드에 도달해야 한다

 

https://kimvampa.tistory.com/79

[Java][1]LinkedList란?

링크드 리스트는 element와 element 간의 연결(Link)을 통해 리스트를 구현한 자료구조다. 배열을 통해 리스트를 구현한 ArrayList와 대비된다. ArrayList에선 각 데이터를 담은 요소들을 element라고 표현했지만 링크드 리스트는 각각의 요소들이 연결이란 특성을 갖기 때문에 node(마디, 교점) 혹은 vertex(꼭지점, 정점)라고 표현한다. 이런 노드를 표현하기 위해 객체지향 프로그래밍 언어에선 객체를 사용한다...(중략)...링크드 리스트의 경우 데이터가 저장되는 하나하나의 요소들이 주소값을 차지한다. 이런 개개의 요소들은 링크드 리스트에서 노드라고 표현되는데 이렇게 흩어진 노드들은 각 노드들이 다음 노드를 지목함으로써 데이터들 간에 관계를 가지게 된다. 링크드 리스트에서 지정한 값을 찾기 위해서든 값을 추가, 삭제하든 반드시 1번째 노드 값을 알아야만 데이터를 다룰 수 있다. 따라서 1번째 노드를 가리키는 head는 링크드 리스트에서 매우 중요하다

 

아래는 링크드 리스트의 예제 코드다. 물론 자바에서 따로 지원하지만 내부는 어떻게 동작하는지 확인하기 위해 예제 코드를 찾아서 가져왔다.

public class LinkedList {
    private Node headNode;
    private int size;

    public LinkedList() {
        headNode = new Node();
        size = 0;
    }

    public void addFirst(Object data) {
        Node newNode = new Node(data);
        newNode.nextNode = headNode.nextNode;
        headNode.nextNode = newNode;
        size++;
    }

    public Object get(int index) {
        return getNode(index).data;
    }

    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index : " + index + ", size : " + size);
        } else {
            Node node = headNode.nextNode;
            for (int i = 0; i < index; i++) {
                node = node.nextNode;
            }

            return node;
        }
    }

    public void add(int index, Object data) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("index : " + index + ", size : " + size);

        Node newNode = new Node(data);
        Node prevNode = getNode(index - 1);
        newNode.nextNode = prevNode.nextNode;
        prevNode.nextNode = newNode;
        size++;
    }

    public Object removeFirst() {
        Node node = headNode.nextNode;
        headNode.nextNode = node.nextNode;
        Object result = node.data;
        size--;
        return result;
    }

    public Object removeNode(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("index : " + index + ", size : " + size);
        else if (index == 0)
            return removeFirst();

        Node prevNode = getNode(index - 1);
        Node removeNode = prevNode.nextNode;
        Node postNode = removeNode.nextNode;
        prevNode.nextNode = postNode;
        Object result = removeNode.data;
        size--;
        return result;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("[");
        Node node = headNode.nextNode;
        if (node == null) {
            result.append("데이터가 없습니다");
        } else {
            result.append(node.data);
            node = node.nextNode;
            while (node != null) {
                result.append(", ");
                result.append(node.data);
                node = node.nextNode;
            }
        }
        result.append("]");
        return result.toString();
    }

    class Node {
        private Node nextNode;
        private Object data;

        public Node() {}

        public Node(Object data) {
            this.nextNode = null;
            this.data = data;
        }
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addFirst(500);
        list.addFirst(400);
        list.addFirst(300);
        list.addFirst(200);
        list.addFirst(100);
        System.out.println(list);

        list.add(1, 150);
        System.out.println(list);

        list.removeNode(1);
        System.out.println(list);
        System.out.println(list.size);

        list.removeFirst();
        System.out.println(list);

        System.out.println(list.get(2));
    }

}