단일 연결 목록 구현

Big O 표기법을 이해하고 있다고 가정합니다. 예제는 JavaScript에 있습니다. 정보 참고자료 Gayle Laakmann McDowell의 "코딩 인터뷰 크래킹"

단일 연결 목록 이해

연결 리스트는 노드의 시퀀스를 나타내는 데이터 구조입니다. 단일 연결 리스트에서 각 노드는 다음 노드를 가리킵니다.

인덱싱에 의존하지 않기 때문에 메모리에서 이러한 노드는 연속적으로(서로 인접하여) 정렬될 필요가 없습니다. 연결된 목록을 반복할 때 null 포인터에 도달할 때까지 노드의 각 참조

를 통과합니다.

노드의 구조

단일 연결 목록에서 각 노드에는 일반적으로 두 개의 필드가 포함됩니다.

• 데이터: 노드에 포함된 값이나 정보
• next: 목록의 다음 노드에 대한 참조(포인터)

머리와 꼬리 포인터

헤드는 목록의 첫 번째 노드에 대한 참조입니다. 연결된 목록의 시작 부분에 대한 액세스를 허용하므로 필수적입니다. 때로는 헤드에 삽입하는 것과 같은 더 쉬운 작업을 위해 센티넬 노드(실제 헤드 노드 앞에 배치) 역할을 합니다. 꼬리는 목록의 마지막 노드에 대한 참조입니다. 다음 포인터는 목록의 끝을 나타내는 null입니다.

삽입/삭제의 메모리 효율성

배열에 비해 연결 목록은 요소의 "이동"이 필요하지 않기 때문에 삽입/삭제 측면에서 메모리 효율성이 더 높습니다. 연결된 목록의 어느 위치에서나 요소를 추가하거나 제거하는 작업에는 이 소요됩니다. $O(1)$O(1) 시간. 그러나 소요되는 시간은 $O(n)$O(n) 최악의 경우 연결된 목록을 통과하여 요소를 추가/제거하는 데 걸리는 시간입니다(첫 번째 요소 추가/제거에는 적용되지 않음).

연결된 목록에는 각 노드에 데이터와 함께 포인터가 저장되기 때문에 추가 메모리 오버헤드가 있다는 점을 지적할 가치가 있습니다.

시간 복잡도 분석

삽입:

• 시작 또는 끝(머리/꼬리 포인터 포함) → $O(1)$O(1)
• 특정 위치에서(순회로 인해) → $O(n)$O(n)

삭제:

• 처음에 → $O(1)$O(1)
• 끝에 → $O(n)$O(n)
• 특정 위치에서 → $O(n)$O(n)

순회/검색: $O(n)$O(n)

자바스크립트 구현

클래식 OOP

class ListNode {
    constructor(val, nextNode = null) {
        this.val = val;
        this.next = nextNode;
    }
}

class LinkedList {
    constructor() {
        // sentinel node for easy operations on head
        this.head = new ListNode(-1);
        this.tail = this.head;
    }

    // get the value at the specified index.
    get(index) {
        let curr = this.head.next;
        let i = 0;
        while (curr !== null) {
            if (i === index) return curr.val;
            curr = curr.next;
            i++;
        }
        return -1;
    }

    // insert a new value at the head of the list.
    insertHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head.next;
        this.head.next = newNode;
        if (newNode.next === null) {
            this.tail = newNode;
        }
    }

    // insert a new value at the tail of the list.
    insertTail(val) {
        const newNode = new ListNode(val);
        this.tail.next = newNode;
        this.tail = newNode;
    }

    // remove the node at the specified index.
    remove(index) {
        let curr = this.head;
        let i = 0;
        while (i < index && curr.next !== null) {
            i++;
            curr = curr.next;
        }

        if (curr !== null && curr.next !== null) {
            if (curr.next === this.tail) this.tail = curr;
            curr.next = curr.next.next;
            return true;
        }
        return false;
    }

    // get all values in the list as an array.
    getValues() {
        const values = [];
        let curr = this.head.next;
        while (curr !== null) {
            values.push(curr.val);
            curr = curr.next;
        }
        return values;
    }

    // get the length of the list.
    length() {
        let length = 0;
        let curr = this.head.next;
        while (curr !== null) {
            length++;
            curr = curr.next;
        }
        return length;
    }
}

기능적 OOP

function ListNode(val, nextNode = null) {
    this.val = val;
    this.next = nextNode;
}

function LinkedList() {
    this.head = new ListNode(-1); // Sentinel node
    this.tail = this.head;
}

// get the value at the specified index
LinkedList.prototype.get = function(index) {
    let curr = this.head.next;
    let i = 0;
    while (curr !== null) {
        if (i === index) return curr.val;
        curr = curr.next;
        i++;
    }
    return -1;
};

// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head.next;
    this.head.next = newNode;
    if (newNode.next === null) {
        this.tail = newNode;
    }
};

// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
    const newNode = new ListNode(val);
    this.tail.next = newNode;
    this.tail = newNode;
};

// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
    let curr = this.head;
    let i = 0;
    while (i < index && curr.next !== null) {
        i++;
        curr = curr.next;
    }

    if (curr !== null && curr.next !== null) {
        if (curr.next === this.tail) this.tail = curr;
        curr.next = curr.next.next;
        return true;
    }
    return false;
};

// get all values in the list as an array
LinkedList.prototype.getValues = function() {
    const values = [];
    let curr = this.head.next;
    while (curr !== null) {
        values.push(curr.val);
        curr = curr.next;
    }
    return values;
};

// get the length of the list
LinkedList.prototype.length = function() {
    let length = 0;
    let curr = this.head.next;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }
    return length;
};

위 내용은 단일 연결 목록 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!