TIL | 링크드 리스트(Linked List)

참고 자료: Jira의 이슈 정렬 방식이 Integer 방식이 아니라고?!

링크드 리스트란?

링크드 리스트(Linked List)는 데이터 요소의 선형 집합을 나타내는 자료 구조입니다. 링크드 리스트는 각 요소가 데이터와 다음 요소를 가리키는 링크(참조)로 이루어져 있습니다. 각 요소를 노드(Node)라고 하며, 노드는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성됩니다. 링크드 리스트에는 여러 종류가 있지만, 가장 일반적인 형태로는 단일 링크드 리스트(Singly Linked List)와 이중 링크드 리스트(Doubly Linked List)가 있습니다.

1. 단일 링크드 리스트(Singly Linked List):

• 각 노드가 데이터와 다음 노드를 가리키는 링크로 이루어진 구조입니다.
• 맨 끝 노드의 링크는 보통 null이며, 리스트의 시작을 나타내는 노드를 헤드(Head)라고 합니다.
• 각 노드는 데이터와 다음 노드를 가리키는 링크 두 가지 필드를 가집니다.

2. 이중 링크드 리스트(Doubly Linked List):

• 각 노드가 데이터와 이전 노드를 가리키는 링크, 그리고 다음 노드를 가리키는 링크로 이루어진 구조입니다.
• 각 노드는 데이터와 이전 노드를 가리키는 링크, 다음 노드를 가리키는 링크 세 가지 필드를 가집니다.
• 이중 링크드 리스트는 단일 링크드 리스트에 비해 각 노드에서 이전 노드로 직접 이동할 수 있는 장점이 있습니다.

링크드 리스트는 데이터의 삽입, 삭제, 검색 등의 작업을 상수 시간이 아니라 선형 시간 또는 선형 시간에 가까운 시간에 수행합니다. 그러나 링크드 리스트는 삽입과 삭제가 배열에 비해 간편하며, 메모리의 동적 할당을 통해 크기가 가변적이므로 크기를 미리 지정할 필요가 없는 장점이 있습니다.

링크드 리스트가 필요한 경우

링크드 리스트는 다음과 같은 상황에서 사용될 수 있습니다:

1. 메모리 관리가 중요한 경우: 링크드 리스트는 동적 메모리 할당을 통해 요소를 저장하므로 메모리 사용을 최적화할 수 있습니다.

2. 삽입 및 삭제가 빈번한 경우: 링크드 리스트는 요소의 삽입 및 삭제가 상수 시간에 가능하므로 이러한 연산이 빈번한 상황에서 유용합니다.

3. 순차적인 데이터 액세스가 필요한 경우: 링크드 리스트는 선형적으로 데이터에 액세스할 수 있으며, 순차적인 데이터 처리에 적합합니다.

4. 크기가 동적으로 변하는 데이터 구조가 필요한 경우: 링크드 리스트는 크기가 동적으로 조절되며, 요소의 추가 및 삭제가 쉽게 이루어지므로 크기가 변하는 데이터 구조를 구현하는 데 적합합니다.

5. 스택이나 큐와 같은 다른 추상 자료형의 구현에 사용되는 경우: 링크드 리스트는 스택이나 큐와 같은 다른 추상 자료형을 구현하는 데 사용될 수 있습니다.

링크드 리스트를 사용하여 이슈 정렬을 뒤바꿔주는 코드 예시

class ListNode {
    value: number;
    next: ListNode | null;

    constructor(value: number) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    head: ListNode | null;

    constructor() {
        this.head = null;
    }

    // 카드를 추가하는 메서드
    addCard(value: number) {
        const newNode = new ListNode(value);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 카드 순서를 뒤바꾸는 메서드
    swapCards(card1: number, card2: number) {
        // 카드1을 찾기
        let prev1: ListNode | null = null;
        let current1: ListNode | null = this.head;
        while (current1 && current1.value !== card1) {
            prev1 = current1;
            current1 = current1.next;
        }

        // 카드2를 찾기
        let prev2: ListNode | null = null;
        let current2: ListNode | null = this.head;
        while (current2 && current2.value !== card2) {
            prev2 = current2;
            current2 = current2.next;
        }

        // 카드1 또는 카드2가 없으면 종료
        if (!current1 || !current2) {
            console.log("카드를 찾을 수 없습니다.");
            return;
        }

        // 카드1과 카드2의 위치를 서로 바꾸기
        if (prev1) {
            prev1.next = current2;
        } else {
            this.head = current2;
        }

        if (prev2) {
            prev2.next = current1;
        } else {
            this.head = current1;
        }

        let temp = current1.next;
        current1.next = current2.next;
        current2.next = temp;
    }

    // 링크드 리스트를 출력하는 메서드
    printList() {
        let current: ListNode | null = this.head;
        while (current) {
            console.log(current.value);
            current = current.next;
        }
    }
}

// 테스트
const linkedList = new LinkedList();
linkedList.addCard(1);
linkedList.addCard(2);
linkedList.addCard(3);
linkedList.addCard(4);

console.log("변경 전:");
linkedList.printList();

linkedList.swapCards(1, 2);

console.log("변경 후:");
linkedList.printList();

이 예제에서는 먼저 ListNode 클래스와 LinkedList 클래스를 정의합니다. 그런 다음 addCard 메서드를 사용하여 카드를 추가하고, swapCards 메서드를 사용하여 두 개의 카드의 순서를 바꿉니다. 마지막으로 printList 메서드를 사용하여 링크드 리스트의 내용을 출력합니다.