• 각 요소들을 노드 형태로 저장하며, 각 노드는 다음 노드를 가리키는 포인터를 포함한 구조

특징

• 동적인 크기 : 요소를 추가하거나 삭제함에 따라 크기를 동적으로 변경할 수 있다
• 데이터 추가, 삭제 용이 : 포인터로 각 요소들을 연결하고 있어, 리스트 중간에 요소를 추가, 삭제하는 과정이 간단하다
• 비연속적 메모리 할당 : 요소들이 반드시 연속적으로 메모리에 위치하지 않아도 되어서 메모리 사용은 유연하다

장점과 단점

• 장점 : 연결 리스트는 포인터로 연결되어 있어, 중간에 데이터를 추가, 삭제할 때 다른 요소들을 이동할 필요가 없다, 삽입, 삭제 작업에 유리한 편
• 단점 : 특정 요소에 접근하려면 순차적으로 탐색해야 하므로 O(n) 시간 복잡도를 가져, Array에 비해 느리다
  • 그리고 요소 별로 포인터도 저장해야 하므로 메모리 추가 공간을 필요로 하게 된다

예시 코드

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

function addNode(head, value) {
    if (!head) return new ListNode(value);

    let current = head;
    while (current.next !== null) {
        current = current.next;
    }
    current.next = new ListNode(value);
    return head;
}

function printList(head) {
    let current = head;
    let values = [];
    while (current) {
        values.push(current.value);
        current = current.next;
    }
    console.log(values.join(" "));
}

let head = new ListNode(1);
head = addNode(head, 3);
head = addNode(head, 5);
printList(head);