Linked List (연결 리스트)

LinkedList란?

연결 리스트, 링크드 리스트(linked list)

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조

 

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

연결 리스트의 성질

• k번째 원소를 확인/변경하기 위해 O(k)가 필요함
• 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

 

연결 리스트의 종류

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

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

• 원형 연결 리스트 (Circular Linked List)

 

배열 vs 연결 리스트 (선형 자료구조)

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(K)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(Overhead)	-	O(N)

 

임의의 위치에 있는 원소를 확인/변경, O(N)

43을 찾는 과정

임의의 위치에 원소를 추가, O(1)

43에 80을 추가

임의의 위치에 원소를 제거, O(1)

43을 제거

 

임의의 위치에 있는 원소를 확인/변경 = O(N)

임의의 위치에 원소를 추가/임의 위치의 원소 제거 = O(1)

LinkedList의 대표적인 사용처 = 메모장등의 텍스트 에디터

 

LinkedList 구현하기

public class LinkedList<T> {

    private Node<T> head;
    private int size;

    private static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    public LinkedList() {
        this.head = null;
        this.size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
        size++;
    }

    public void addLast(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Invalid index");
        }
        if (index == 0) {
            addFirst(data);
        } else if (index == size) {
            addLast(data);
        } else {
            Node<T> newNode = new Node<>(data);
            Node<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
            size++;
        }
    }

    public T getFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        return head.data;
    }

    public T getLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        Node<T> current = head;
        while (current.next != null) {
            current = current.next;
        }
        return current.data;
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Invalid index");
        }
        Node<T> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    public T removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        T data = head.data;
        head = head.next;
        size--;
        return data;
    }

    public T removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("List is empty");
        }
        if (size == 1) {
            return removeFirst();
        }
        Node<T> current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        T data = current.next.data;
        current.next = null;
        size--;
        return data;
    }

    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Invalid index");
        }
        if (index == 0) {
            return removeFirst();
        }
        if (index == size - 1) {
            return removeLast();
        }
        Node<T> current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        T data = current

메모리 누수를 감안한 구현 코드

import java.util.*;

public class Main {
    static final int MX = 1000005;
    static int[] dat = new int[MX];
    static int[] pre = new int[MX];
    static int[] nxt = new int[MX];
    static int unused = 1;

    static void insert(int addr, int num) {
        dat[unused] = num;
        pre[unused] = addr;
        nxt[unused] = nxt[addr];
        if(nxt[addr] != -1) pre[nxt[addr]] = unused;
        nxt[addr] = unused;
        unused++;
    }

    static void erase(int addr) {
        nxt[pre[addr]] = nxt[addr];
        if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
    }

    static void traverse() {
        int cur = nxt[0];
        while(cur != -1) {
            System.out.print(dat[cur] + " ");
            cur = nxt[cur];
        }
        System.out.println("\n");
    }

    static void insert_test() {
        System.out.println("****** insert_test *****");
        insert(0, 10); // 10(address=1)
        traverse();
        insert(0, 30); // 30(address=2) 10
        traverse();
        insert(2, 40); // 30 40(address=3) 10
        traverse();
        insert(1, 20); // 30 40 10 20(address=4)
        traverse();
        insert(4, 70); // 30 40 10 20 70(address=5)
        traverse();
    }

    static void erase_test() {
        System.out.println("****** erase_test *****");
        erase(1); // 30 40 20 70
        traverse();
        erase(2); // 40 20 70
        traverse();
        erase(4); // 40 70
        traverse();
        erase(5); // 40
        traverse();
    }

    public static void main(String[] args) {
        Arrays.fill(pre, -1);
        Arrays.fill(nxt, -1);
        insert_test();
        erase_test();
    }
}

 

---

LinkedList 위키백과 정보

 

en.wikipedia.org/wiki/Linked_listen.wikipedia.org/wiki/Linked_list

Linked list - Wikipedia

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

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