자료구조 - Singly Linked List

Linked List

---

💡 Linked List란?

• Linked List란 각 노드가 데이터와 포인터를 가지고 있는 자료구조입니다. 데이터를 담고 있는 각 노드들은 포인터를 통해 이전 노드와 다음 노드를 연결하고 있고, 데이터를 추가하거나 삭제할 때 포인터의 주소값만 변경이 발생하므로 데이터 삽입/삭제 시 용이합니다.
  반면 ArrayList인 경우 중간에 데이터를 삽입/삭제 시 전체 인덱스가 한 칸씩 뒤로 밀리거나 당겨지므로 Linked List에 비해 성능이 떨어집니다. 
• 또한 Linked List는 인덱스가 없기 때문에 특정 요소에 접근하기 위해서는 순차 탐색이 필요하므로 탐색 속도가 늦어진다는 단점이 있습니다. 반면 Array List는 인덱스가 있기 때문에 특정 요소에 접근하기 용이합니다. 

 

💡 Linked List의 탄생 배경

• LinkedList 클래스는 ArrayList 클래스가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었습니다. 
  ArrayList는 각 요소가 순차적으로 저장되지만 LinkedList는 저장된 요소가 비순차적으로 분포되며, 각 요소들을 Link로 연결하여 구성하고 있습니다. 

 

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

• 다음 요소만을 가리키는 참조를 가지고 있는 Linked List를 단일 연결 리스트라고 하며, 단일 연결 리스트는 요소의 저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경하면 되므로 아주 빠르게 처리될 수 있지만 인덱스를 가지고 있지 않기 때문에 임의의 원소에 접근하는 것이 불가능합니다.(randomAccess 불가능)

단일 연결 리스트 구조

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

• 단일 연결 리스트는 다음 요소의 참조값만 가지고 있으므로 이전 요소로 접근하는데 매우 어렵다고 합니다. 따라서 이전 요소를 가리키는 참조도 가질 수 있는 이중 연결 리스트를 더 많이 사용한다고 합니다. JAVA에서 LinkedList는 ArrayList와 달리 List 인터페이스를 구현한 AbstractList를 상속하는 게 아닌 AbstractSequentialList를 상속받는다고 합니다.

이중 연결 리스트 구조

 

💡 시간 복잡도

• 탐색
  • 인덱스를 가지고 있지 않기 때문에 O(n)의 시간 복잡도를 가집니다.
• 삽입
  • 자신이 추가하려는 위치의 이전 노드를 아는 경우 O(1)의 시간 복잡도를 가지지만 모르는 경우에는 추가하려는 위치의 이전 노드를 탐색해야 하므로 O(n)의 시간 복잡도를 가집니다.
• 삭제
  • 이중 연결 리스트의 경우 제거할 위치의 노드만 안다면, 바로 이전 노드가 가리키는 노드를 변경해주면 되기 때문에 O(1)의 시간 복잡도를 가집니다.
  • 단일 연결 리스트의 경우 이전 노드로 가는 포인터가 없기 때문에 제거하려는 위치를 알아도 O(n)의 시간 복잡도를 가지게 됩니다.
• 수정
  • 인덱스를 통해 데이터를 관리하지 않기 때문에 특정 노드를 일단 찾고 데이터를 수정해야하기 때문에 O(n)의 시간 복잡도를 가집니다.

 

Linked List 구현

---

• 데이터가 없는 시작 노드를 가집니다. 첫 노드는 단지, 다음 노드를 가리키는 역할만 수행합니다.

 

💡 Node 클래스

• 간결하게 보기 위해 @Getter, @Setter 어노테이션을 사용하였습니다. 그리고 기본 생성자와 데이터를 주입받는 생성자가 있습니다.

@Getter
@Setter
public class Node {

    private int data;
    private Node next;

    public Node() { }

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

 

💡 Linked List 클래스

public class LinkedList {

    private Node head;

    public LinkedList() {
        this.head = new Node();
    }

    /**
     * 마지막에 새로운 노드를 추가합니다.
     */
    public void append(int data) {
        Node first = this.head;
        Node tail = new Node(data);

        while (first.getNext() != null) {
            first = first.getNext();
        }
        first.setNext(tail);
    }

    /**
     * 특정 인덱스에 새로운 노드 추가
     */
    public void append(int index, int data) {
        Node node = this.head.getNext();
        Node newNode = new Node(data);
        if (index == 0) {
            this.head.setNext(newNode);
            newNode.setNext(node);
        } else {
            for (int i = 0; i < index -1; i++) {
                node = node.getNext();
            }
            newNode.setNext(node.getNext()); // 새로운 노드뒤에 이어붙이기
            node.setNext(newNode);           // 기존 노드 뒤에 새로운 노드 붙이기
        }
    }

    /**
     * 특정 인덱스의 노드 삭제
     */
    public void remove(int index) {
        Node node = this.head.getNext();

        if (0 == index) {
            this.head.setNext(node.getNext());
        } else {
            for (int i = 0; i < index - 1; i++) {
                node = node.getNext();
            }
            node.setNext(node.getNext().getNext());
        }
    }

    /**
     * 특정 노드 삭제
     */
    public void removeNode(Node node) {
        if (node == null || node.getNext() == null) {
            return;
        }
        Node next = node.getNext();
        node.setData(next.getData());
        node.setNext(next.getNext());
    }

    /**
     * 특정 인덱스의 Node 반환
     */
    public Node get(int index) {
        Node first = this.head.getNext();
        for (int i = 1; i <= index; i++) {
            first = first.getNext();
        }
        return first;
    }

    /**
     * 특정 값을 기준으로 나누기
     */
    public Node partition(int x) {
        Node n = this.head.getNext();
        Node head = n;
        Node tail = n;

        while (n != null) {
            Node next = n.getNext();
            if (n.getData() < x) {
                n.setNext(head);
                head = n;
            } else {
                tail.setNext(n);
                tail = n;
            }
            n = next;
        }
        tail.setNext(null); // 마지막임을 표시하기 위해
        return head;
    }

    /**
     * 현재 모든 노드 출력
     */
    public void print() {
        Node first = this.head.getNext();

        while (first.getNext() != null) {
            System.out.print(first.getData() + " -> ");
            first = first.getNext();
        }
        System.out.println(first.getData());
    }
}

 

💡 append(int data) 함수의 흐름

💡 append(int index, int data) 함수의 흐름

• node 변수는 첫 시작점이 아닌 실제 데이터가 있는 노드를 시작점으로 잡습니다.
• 추가하고자 하는 데이터를 첫 시작점으로 잡는다면 즉 index가 0이라면, 치환을 사용하여 데이터의 자리를 변경해줍니다.
• 새로운 노드 뒤에 기존 노드들을 이어붙입니다.
• 기존 노드에 새로운 노드를 이어 붙입니다.

💡 remove(int index) 함수의 흐름

• index가 0이라면 시작점의 노드의 next가 2번째 노드부터 시작되도록 설정합니다.
• index가 0이 아니라면 O(n)만큼 순회 후 노드의 next 연결점을 수정해줍니다.

💡 removeNode(Node node) 함수의 흐름

• 삭제하려는 노드의 다음 노드를 찾아서 이전 노드에 연결시켜줍니다.

 

Linked List 테스트 결과

---

public class Main {

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

        System.out.println("=====> 마지막에 새로운 노드 추가 <=====");
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);
        linkedList.append(5);
        linkedList.print();

        System.out.println("=====> 특정 인덱스에 새로운 노드 추가 <=====");
        linkedList.append(1, 10);
        linkedList.print();

        System.out.println("=====> 특정 인덱스의 노드 삭제 <=====");
        linkedList.remove(0);
        linkedList.print();

        System.out.println("=====> 특정 노드 삭제 <=====");
        linkedList.removeNode(linkedList.get(1));
        linkedList.print();

        System.out.println("=====> 특정 값을 기준으로 나누기 <=====");
        Node n = linkedList.partition(5);
        while (n.getNext() != null) {
            System.out.print(n.getData() + " -> ");
            n = n.getNext();
        }
        System.out.println(n.getData());
    }
}

 

✔️ 정리

• Linked List를 만들어 보면서 탐색, 삽입, 삭제의 시간 복잡도에서 왜 O(n) 만큼의 시간이 소요되는지 파악할 수 있었습니다.

 

참고 자료)

https://www.youtube.com/@eleanorlim/playlists

https://www.nextree.co.kr/p6506/