Xinrui's personal website that shares my work and thoughts

Doubly Linked List

TypeScript Data Structure: Implementing a Doubly Linked List

用Typescript实现一个双向链表

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

  • MyLinkedList() Initializes the MyLinkedList object.
  • int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
  • void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • void addAtTail(int val) Append a node of value val as the last element of the linked list.
  • void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
  • void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

  • 0 <= index, val <= 1000
  • Please do not use the built-in LinkedList library.
  • At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Analysis of Doubly Linked List Implementation

In computer science, linked lists are a fundamental data structure, and a doubly linked list is a variation that allows traversal in both directions—forward and backward. Each node in a doubly linked list contains a reference to both the next and the previous node, providing flexibility and efficiency for operations that require frequent access to both ends of the list.

Requirements Analysis

In this task, the goal is to implement a doubly linked list with basic functionalities such as:

  • Retrieving the value of the node at a specific index.
  • Inserting a node at the beginning of the list.
  • Inserting a node at the end of the list.
  • Inserting a new node at a specified position in the list.
  • Deleting a node at a specified index.

Thought Process and Algorithm Implementation

1. Initialization

We start by defining a Node class, which will have three properties: val (the value stored in the node), next (a reference to the next node), and prev (a reference to the previous node). We also define a MyLinkedList class to manage these nodes, including properties for the head (the first node), tail (the last node), and size (the length of the list).

class Node {
    val: number;
    next: Node | null;
    prev: Node | null;

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

2. Retrieving a Node Value

The get method straightforwardly traverses the list from the head to the desired index. It’s important to handle invalid indices by returning -1 if the index is out of bounds.

get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let current = this.head;
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    return current.val;
}

3. Adding a Node at the Head

When adding at the head, we create a new node and adjust the head pointer to point to this new node. If the list is not empty, we also need to update the previous head’s prev to reference the new node. If the list is empty, the new node also becomes the tail.

addAtHead(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
    this.size++;
}

4. Adding a Node at the Tail

Adding at the tail involves creating a new node and adjusting the tail pointer. The new node’s prev points to the current tail, and if the list is empty, the new node will serve as both the head and tail.

addAtTail(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.size++;
}

5. Inserting a Node at a Specified Position

This operation is more complex, as it involves handling several cases:

  • Inserting at index 0, which is equivalent to addAtHead.
  • Inserting at index size, equivalent to addAtTail.
  • For other positions, find the node before the desired position and insert the new node accordingly.
addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.size) return;
    if (index == 0) {
        this.addAtHead(val);
    } else if (index == this.size) {
        this.addAtTail(val);
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const newNode = new Node(val);
        newNode.next = prev.next;
        newNode.prev = prev;
        if (prev.next) {
            prev.next.prev = newNode;
        }
        prev.next = newNode;
        this.size++;
    }
}

6. Deleting a Node at a Specified Position

Deletion requires careful pointer adjustments. Special attention is needed when deleting the head or tail node to update the head and tail pointers accordingly.

deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    if (index === 0) {
        this.head = this.head.next;
        if (this.head) {
            this.head.prev = null;
        } else {
            this.tail = null; // list became empty
        }
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const toDelete = prev.next;
        prev.next = toDelete.next;
        if (prev.next) {
            prev.next.prev = prev;
        } else {
            this.tail = prev; // deleting the last node
        }
    }
    this.size--;
}

Conclusion

This analysis not only illustrates how to implement each fundamental operation of a doubly linked list but also discusses handling edge cases and special conditions. Understanding these operations is key to mastering the linked list data structure. Hopefully, this breakdown will help you gain a deeper understanding of the implementation and application of doubly linked lists.

双向链表的实现分析

在计算机科学中，链表是一种常用的数据结构，双向链表是链表的一种变形，其中每个节点除了有指向下一个节点的指针next外，还包含一个指向上一个节点的指针prev。这种结构提供了向前和向后两种遍历方式，使得某些操作更为高效。

需求分析

在这个题目中，需要实现一个双向链表，包括以下基本操作：

  • 获取链表中第index个节点的值。
  • 在链表头部插入一个节点。
  • 在链表尾部插入一个节点。
  • 在链表中的第index个位置插入一个新节点。
  • 删除链表中的第index个节点。

思维过程与算法实现

1. 初始化

首先，我们需要一个Node类来定义节点，包括val（节点存储的值），next（指向下一个节点的引用）和prev（指向上一个节点的引用）。其次，定义MyLinkedList类来管理这些节点，包括head（头节点），tail（尾节点），以及size（链表长度）。

class Node {
    val: number;
    next: Node | null;
    prev: Node | null;

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

2. 获取节点值

获取节点值的操作相对直接，从head开始，遍历链表直到到达指定的index位置。需要注意的是，如果index无效（即超出链表范围），则返回-1。

get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let current = this.head;
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    return current.val;
}

3. 添加节点到头部

在头部添加节点时，需要创建一个新节点，并将其next指针指向当前的head。同时，如果链表本身不为空，更新原有头节点的prev指向新节点。如果链表为空，则同时更新tail。

addAtHead(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
    this.size++;
}

4. 添加节点到尾部

尾部添加类似于头部添加，但是新节点的prev将指向当前的tail，并更新tail的next。

addAtTail(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.size++;
}

5. 在指定位置添加节点

这是一个稍微复杂的操作，需要分多种情况处理：

  • 如果index等于0，相当于addAtHead。
  • 如果index等于size，相当于addAtTail。
  • 其他情况，需要找到第index-1个节点，然后在其后插入新节点。
addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.size) return;
    if (index === 0) {
        this.addAtHead(val);
    } else if (index === this.size) {
        this.addAtTail(val);
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const newNode = new Node(val);
        newNode.next = prev.next;
        newNode.prev = prev;
        prev.next.prev = newNode;
        prev.next = newNode;
        this.size++;
    }
}

6. 删除指定位置的节点

删除操作需要更新prev和next指针。特别要注意当删除的是头节点或尾节点时，还需要更新head或tail。

deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    if (index === 0) {
        this.head = this.head.next;
        if (this.size === 1) {
            this.tail = null;
        } else {
            this.head.prev = null;
        }
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const toDelete = prev.next;
        prev.next = toDelete.next;
        if (prev.next) {
            prev.next.prev = prev;
        } else {
            this.tail = prev;
        }
    }
    this.size--;
}

总结

通过逐步解析每个操作，我们不仅展示了如何实现双向链表的各个基本功能，还深入讨论了边界情况和特殊情况的处理。理解这些基本操作是掌握链表数据结构的关键。希望这篇分析可以帮助你更好地理解双向链表的实现和应用。

Full Code, this code can also be used at Leetcode 707. Design Linked List

class Node {
    val: number;
    next: Node;
    prev: Node;

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

class MyLinkedList {
    
    size: number;
    head: Node;
    tail: Node;
    
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    get(index: number): number {
        if (index < 0 || index >= this.size ) return -1;
        let curr = this.head;
        while (index > 0) {
            curr = curr.next;
            index--;
        }
        return curr.val;
    }

    addAtHead(val: number): void {
        let newHead = new Node(val);
        if (this.size === 0) {
            this.head = newHead;
            this.tail = newHead;
        } else {
            this.head.prev = newHead;
            newHead.next = this.head;
            this.head = newHead;
        }
        this.size++;
    }

    addAtTail(val: number): void {
        let newTail = new Node(val);
        if (this.size === 0) {
            this.head = newTail;
            this.tail = newTail;
        } else {
            this.tail.next = newTail;
            newTail.prev = this.tail;
            this.tail = newTail;
        }
        this.size++;
    }

    addAtIndex(index: number, val: number): void {
        if (index < 0 || index > this.size) return;
        if (index === 0) {
            this.addAtHead(val);
        } else if (index === this.size) {
            this.addAtTail(val);
        } else {
            let newNode = new Node(val);
            let prev = this.head;
            while (index - 1 > 0) {
                prev = prev.next;
                index--;
            }
            newNode.prev = prev;
            newNode.next = prev.next;
            prev.next.prev = newNode;
            prev.next = newNode;
            this.size++;
        }
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) return;
        if (index === 0) {
            this.head = this.head.next;
            if (this.size === 1) {
                this.tail = null;
            }
            this.size--;
        } else {
            let prev = this.head;
            while (index - 1 > 0) {
                prev = prev.next;
                index--;
            }
            prev.next = prev.next.next;
            if (prev.next) { // tail 不变
                prev.next.prev = prev;
            } else {
                this.tail = prev;
            }
            this.size--;   
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.