📅 2025-10-29

➡️ 자료구조 연결리스트에 대해 새롭게 알게 된 것 또는 헷갈리는 부분 정리

---

🔎 학습 리마인드

📌 연결 리스트 (Linked List)

💡 개념

• 데이터를 포인터(참조)를 이용해 서로 연결하는 선형 자료구조
• 각 데이터 단위를 노드라고 부르며, 각 노드는 값(value)과 다음 노드에 대한 참조(next)를 가지고 있음
• 연결 리스트의 가장 첫 번째 지점을 헤드(head)라 부름
  • 헤드는 연결 리스트의 첫 번째 노드를 의미
• 마지막 노드는 가리킬 것이 없으니 null을 가리킴

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

💡 장점 & 단점

장점

• 중간 삽입/삭제가 효율적
• 크기가 유연하게 변함

단점

• 인덱스로 즉시 접근 불가
• 포인터 저장으로 인한 추가 메모리 사용

💡 Node 구현

class Node {
  constructor(data, next = null, length) {
    this.data = data;
    this.next = next;
  }
}

💡 add 구현

• 리스트가 비어있는 경우
  • head가 null → 새 노드를 head로 설정
• 리스트에 이미 노드가 있는 경우
  • 마지막 노드까지 순회 → 마지막 노드의 next에 새 노드를 연결

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }

    add(value){
        const newNode = new Node(value);

        if (!this.head) {
            // 리스트가 비어 있으면, head가 새 노드
            this.head = newNode;
        } else {
            // 마지막 노드까지 이동
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            // 마지막 노드의 next에 새 노드 연결
            current.next = newNode;
        }

        this.length++;
        console.log(JSON.stringify(list, null, this.length));
    }

    remove() {}
    search() {}
}

💡 search 구현

search(index) {
    let current = this.head;
    let count = 0;

    // index 값까지 이동
    while (count < index) {
        current = current.next;
        count++
    }

    // current가 존재하면 data 반환, 없으면 null
    return current ? current.data : null;
}

💡 remove 구현

remove(value) {
    if (!this.head) return;

    // head가 삭제 대상이면
    if (this.head.data === value) {
        this.head = this.head.next;
        this.length--;
        return;
    }

    let current = this.head;

    while (current.next) {
        if (current.next.data === value) {
            current.next = current.next.next;
            this.length--;
            return;
        }
        current = current.next;
    }
}

---