[자료구조] Linked List

Linked List

연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조

(포인터를 사용해서 연결된다)

각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성

왜 Linked List를 사용하나?

배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음

1) 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함

2) 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간을 만들고, 기존 요소 전부 이동)

장점

1) 동적 크기

2) 삽입/삭제 용이

단점

1) 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능)

2) 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요

노드 구현은 아래와 같이 데이터와 다음 노드에 대한 참조로 나타낼 수 있다

class Node {
    int data;
    Node next;

    // Node constructor
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Single Linked List

노드 3개를 잇는 코드를 만들어보자

      head         second         third 
        |             |             | 
        |             |             | 
    +---+---+     +---+---+     +----+----+ 
    | 1  | o----->| 2 | o-----> |  3 |  # | 
    +---+---+     +---+---+     +----+----+

LinkList 구현

public class LinkedList {
    Node head;  // 첫번째 노드를 가리키는 head 변수

    static class Node {
        int data;  // 노드의 데이터
        Node next;  // 다음 노드를 가리키는 변수

        Node(int d) {
            data = d;
            next = null;
        }
    }

    // 연결 리스트의 앞쪽에 노드를 추가
    public void push(int newData) {
        Node newNode = new Node(newData);  // 새 노드 생성
        newNode.next = head;  // 새 노드의 next를 현재 head로 설정
        head = newNode;  // head를 새 노드로 갱신
    }

    // 주어진 노드 다음에 새 노드를 추가
    public void insertAfter(Node prevNode, int newData) {
        if (prevNode == null) {
            System.out.println("이전 노드는 null일 수 없습니다.");
            return;
        }
        Node newNode = new Node(newData);  // 새 노드 생성
        newNode.next = prevNode.next;  // 새 노드의 next를 이전 노드의 next로 설정
        prevNode.next = newNode;  // 이전 노드의 next를 새 노드로 갱신
    }

    // 연결 리스트의 끝에 노드를 추가
    public void append(int newData) {
        Node newNode = new Node(newData);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    // 주어진 키를 가진 노드를 삭제
    public void deleteNode(int key) {
        Node temp = head, prev = null;

        if (temp != null && temp.data == key) {  // head 노드가 삭제할 노드와 일치할 경우
            head = temp.next;
            return;
        }

        while (temp != null && temp.data != key) {  // 삭제할 노드를 찾을 때까지 반복
            prev = temp;
            temp = temp.next;
        }

        if (temp == null) return;  // 키와 일치하는 노드가 없을 경우 반환

        prev.next = temp.next;  // 일치하는 노드를 건너뛰게 연결
    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

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

        llist.append(1);
        llist.append(3);
        llist.push(0);
        llist.insertAfter(llist.head.next, 2);  // "0 1 2 3" 순으로 출력 

        llist.printList();

        llist.deleteNode(2);  // 2를 삭제하면 "0 1 3" 순으로 출력

        llist.printList();
    }
}