링크드 리스트

[lukasjhan]

링크드 리스트

링크드 리스트는 데이터 요소들을 순차적으로 연결한 자료구조입니다. 각 노드(Node)는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.

주요 특징

• 데이터의 삽입과 삭제가 배열보다 효율적 (O(1))
• 메모리를 동적으로 사용
• 임의 접근이 불가능하며 순차적으로 접근해야 함
• 다음 노드의 참조를 위한 추가 메모리 공간이 필요

연습 문제

• 링크드 리스트 구현
• 링크드 리스트 순회하면서 데이터 출력하기
• 링크드 리스트에서 값 찾기
• 링크드 리스트에서 값 삭제하기
• 링크드 리스트 거꾸로 만들기

예시 코드

class ListNode {
data: T;
next: ListNode | null;

constructor(data: T) {
    this.data = data;
    this.next = null;
}

}

class LinkedList {
head: ListNode | null;

constructor() {
    this.head = null;
}

// 노드 추가
append(data: T): void {
    const newNode = new ListNode(data);
    
    if (!this.head) {
        this.head = newNode;
        return;
    }
    
    let current = this.head;
    while (current.next) {
        current = current.next;
    }
    current.next = newNode;
}

// 노드 출력
print(): void {
    let current = this.head;
    while (current) {
        console.log(current.data);
        current = current.next;
    }
}

// 노드 검색
find(data: T): ListNode<T> | null {
    let current = this.head;
    while (current) {
        if (current.data === data) {
            return current;
        }
        current = current.next;
    }
    return null;
}

// 노드 삭제
delete(data: T): void {
    if (!this.head) return;
    
    if (this.head.data === data) {
        this.head = this.head.next;
        return;
    }
    
    let current = this.head;
    while (current.next) {
        if (current.next.data === data) {
            current.next = current.next.next;
            return;
        }
        current = current.next;
    }
}

// 리스트 뒤집기
reverse(): void {
    let prev: ListNode<T> | null = null;
    let current = this.head;
    let next: ListNode<T> | null = null;
    
    while (current) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    this.head = prev;
}

}