Linked List 개념

Linked List란?

Linked List란 컴퓨터에 자료를 저장하는 구조의 한 종류입니다. 일렬로 연결된 데이터를 저장할 때 사용합니다. 데이터를 저장할 수 있는 공간이 있으면 그 안에 다음 데이터의 주소를 가지고 있는 구조입니다.

배열과 비교

Linked List를 이야기할 때 배열을 빼놓을 수 없습니다. 

배열은 배열 방들이 물리적으로 한 곳에 모여있습니다. 그래서 배열의 방 크기를 한번 정하면 늘이거나 줄일 수가 없습니다. 그에 반해 Linked List는 데이터를 중간에 삽입하고 싶으면 앞에 노드가 가지고 있던 주소를 자기가 갖고 앞에 노드에는 나의 주소를 알려주면 됩니다. 반대로 링크를 빼고 싶다면 해당 노드가 가지고 있던 다음 노드의 주소를 앞에 노드에 주면 됩니다. 그렇게 되면 자연스럽게 해당 노드가 빠지게 됩니다. 해당 노드가 Linked List에서는 삭제가 됐지만 사실 메모리를 사용하고 있습니다. 자바에서는 이렇게 사용되지 않는 변수들을 알아서 처리해주지만, c나 c++에서는 반드시 명시를 해주어야 합니다. Linked List는 이렇게 주소를 일일이 찾아다녀야 하므로 배열보다 느릴 수가 있습니다. 하지만 삽입, 삭제와 같은 기능을 배열로 구현하게 된다면 노드가 한 개 추가될 때마다 배열방을 통째로 다시 선언해야 하기 때문에 길이가 정해지지 않은 데이터를 핸들링 할 때는 Linked List가 좋습니다.

Linked List 단/양방향

Linked List는 길이가 정해져 있지 않은 데이터의 연결된 집합입니다.

단방향

❗️헤더 주소 하나만 포인터를 저장하고 있습니다.

단방향 Linked List는 한쪽 방향으로만 갈 수 있습니다. 오직 자신 다음 노드만 어디있는지 알고 있어서 검색을 할 때에 가장 앞에 있는 노드부터 한개씩 이동하면서 검색을 해야 합니다. 이렇게 한 방향으로만 이동할 수 있는 Linked List를 단방향 Linked List라고 합니다. 

양방향

❗️양쪽 끝에 포인터를 저장하고 있습니다.

반면에 양방향 Linked List는 다음 주소를 가지고 있고 추가로 자신의 앞에 있는 노드가 어디에 있는지를 가지고 있습니다. 그로 인해 앞뒤로 자유롭게 다닐 수가 있습니다. 데이터를 삽입할 때, 노드를 하나 생성하고 삽입하고자 하는 위치의 전 노드의 주소와 전 노드가 가지고 있던 다음 노드의 주소를 생성한 노드에 주입합니다. 또한 다음 노드가 가지고 있던 전 노드의 주소를 자신의 주소로 바꾸게 되면 자연스럽게 삽입을 할 수 있습니다.

이렇게 되면 검색을 할 때 속도적인 측면에서 단방향에 비해 이득을 볼 수 있습니다. 하지만 굳이 양쪽으로 다닐 필요가 없는 데이터 구조를 양방향으로 디자인할 필요는 없습니다. 포인터를 두 개 저장하는 만큼 메모리를 차지하기 때문입니다.

단방향 Linked List 구현(Java)

public class LinkedList {
    Node header;

    static class Node{
        int data;
        Node next = null;
    }

    LinkedList(){
        header = new Node();
    }

    void append(int d){
        Node end = new Node();
        end.data = d;
        Node n = header;
        while(n.next != null){
            n = n.next;
        }
        n.next = end;
    }

    void delete(int d){
        Node n = header;
        while(n.next != null){
            if(n.next.data == d){
                n.next = n.next.next;
            } else{
                n = n.next;
            }
        }
    }
    
    void retrieve(){
        Node n = header.next;
        while(n.next != null){
            System.out.print(n.data + " -> ");
            n = n.next;
        }
        System.out.println(n.data);
    }
}

class LinkedListNode{
    public static void main(String[] args){
        LinkedList ll = new LinkedList();
        ll.append(1);
        ll.append(2);
        ll.append(3);
        ll.append(4);
        ll.retrieve();
        ll.delete(1);
        ll.retrieve();
    }
}