【js版数据结构之链表】

一、认识链表

采用链式存储方式存储的线性表称为链表，链表是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻， 必须采用附加信息表示数据元素之间的逻辑关系，因此链表的每一个结点不仅包含元素本身的信息数据域,而且包含元素之间逻辑关系的信息，即逻辑上相邻结点地址的指针域。

二、顺序表与链表的比较

三、单链表

单链表是指结点中只包含一个指针域的链表，指针域中储存着指向后继结点的指针。单链表的头指针是线性表的起始地址，是线性表中第一个数据元素的存储地址，可作为单链表的唯一标识。单链表的尾结点没有后继结点，所以其指针域值为None。

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

class LinkedList {
 constructor() {
   this.head = null; // 头节点
   this.count = 0; // 链表长度
 }

 // 在链表末尾插入元素
 push(element) {
   const node = new Node(element);

   if (this.head === null) {
     this.head = node; // 如果链表为空，将新节点设置为头节点
   } else {
     let current = this.head;

     while (current.next !== null) {
       current = current.next; // 找到链表的最后一个节点
     }

     current.next = node; // 将新节点链接到最后一个节点
   }

   this.count++; // 链表长度加1
 }

 // 根据索引删除节点
 removeAt(index) {
   if (index >= 0 && index < this.count) {
     let current = this.head;

     if (index === 0) {
       this.head = current.next; // 如果要删除的是头节点，将头节点指向下一个节点
     } else {
       let previous;
       for (let i = 0; i < index; i++) {
         previous = current;
         current = current.next; // 找到要删除的节点及其前一个节点
       }

       previous.next = current.next; // 将前一个节点的next指针指向要删除节点的下一个节点
     }

     this.count--; // 链表长度减1
     return current.element; // 返回删除的节点元素值
   }

   return;
 }

 // 根据索引获取节点
 getNodeAt(index) {
   if (index >= 0 && index < this.count) {
     let node = this.head;

     for (let i = 0; i < index; i++) {
       node = node.next; // 遍历链表找到对应索引的节点
     }
     return node;
   }
   return;
 }

 // 根据索引删除节点（优化）
 removeAt2(index) {
   if (index >= 0 && index < this.count) {
     let current = this.head;

     if (index === 0) {
       this.head = current.next; // 如果要删除的是头节点，将头节点指向下一个节点
     } else {
       const previous = this.getNodeAt(index - 1); // 获取要删除节点的前一个节点
       current = previous.next; // 获取要删除的节点

       previous.next = current.next; // 将前一个节点的next指针指向要删除节点的下一个节点
     }

     this.count--; // 链表长度减1
     return current.element; // 返回删除的节点元素值
   }

   return;
 }

 // 判断两个元素是否相等的函数
 equalFn(a, b) {
   return JSON.stringify(a) === JSON.stringify(b);
 }

 // 查找元素在链表中的索引
 indexOf(element) {
   let current = this.head;

   for (let i = 0; i < this.count; i++) {
     if (this.equalFn(element, current.element)) {
       return i; // 找到对应元素，返回索引
     }
     current = current.next;
   }

   return -1; // 未找到，返回-1
 }

 // 根据元素值删除节点
 remove(element) {
   const index = this.indexOf(element); // 查找元素在链表中的索引
   return this.removeAt(index); // 根据索引删除节点
 }

 // 在指定位置插入节点
 insert(element, index) {
   if (index >= 0 && index <= this.count) {
     const node = new Node(element);

     if (index === 0) {
       const current = this.head;
       node.next = current; // 将新节点的next指针指向当前的头节点
       this.head = node; // 将新节点设置为头节点
     } else {
       const previous = this.getNodeAt(index - 1); // 获取要插入位置的前一个节点
       const current = previous.next; // 获取要插入位置的当前节点

       node.next = current; // 将新节点的next指针指向当前节点
       previous.next = node; // 将前一个节点的next指针指向新节点
     }

     this.count++; // 链表长度加1
     return true;
   }
   return false;
 }

 // 判断链表是否为空
 isEmpty() {
   return this.size() === 0;
 }

 // 返回链表长度
 size() {
   return this.count;
 }

 // 返回头节点
 getHead() {
   return this.head;
 }
}

四、双链表

双向链表的结点具有两个指针域，一个指针指向前驱结点，一个指针指向后继结点。使得查找某个结点的前驱结点不需要从表头开始顺着链表依次进行查找，减小时间复杂度。

// 双向链表节点类，继承自单向链表节点类
class DoublyNode extends Node { 
    constructor(element) {
        super(element); // 调用父类的构造函数，保存元素值和next指针
        this.prev = null; // 新增prev指针，指向前一个节点
    }
}

// 双向链表类，继承自单向链表类
class DoublyLinkedList extends LinkedList {
    constructor() {
        super(); // 调用父类的构造函数，初始化头节点和链表长度
        this.tail = null; // 新增尾节点指针，指向最后一个节点
    }

    // 在链表末尾插入元素
    push(element) {
        const node = new DoublyNode(element); // 创建新的节点
        if (this.head == null) { // 如果链表为空，将新节点设置为头节点和尾节点
            this.head = node;
            this.tail = node; 
        } else { // 否则，将新节点链接到最后一个节点
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node; // 更新尾节点指针
        }
        this.count++; // 链表长度加1
    }

    // 在指定位置插入节点
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new DoublyNode(element); // 创建新的节点
            let current = this.head;
            if (index === 0) { // 如果要插入到头节点位置
                if (this.head == null) { // 如果链表为空，将新节点设置为头节点和尾节点
                    this.head = node;
                    this.tail = node; 
                } else { // 否则，将新节点链接到当前头节点，并将其设置为新的头节点
                    node.next = this.head;
                    this.head.prev = node; 
                    this.head = node;
                }
            } else if (index === this.count) { // 如果要插入到尾节点位置
                current = this.tail;
                current.next = node;
                node.prev = current;
                this.tail = node; // 更新尾节点指针
            } else { // 否则，在链表中间插入节点
                const previous = this.getNodeAt(index - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
                current.prev = node; // 新增prev指针，连接前一个节点和新节点
                node.prev = previous; 
            }
            this.count++; // 链表长度加1
            return true;
        }
        return false;
    }

    // 根据索引删除节点
    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index === 0) { // 如果要删除头节点
                this.head = this.head.next;

                if (this.count === 1) { // 如果链表只有一个节点，同时更新尾节点指针
                    this.tail = undefined;
                } else {
                    this.head.prev = undefined; // 新增prev指针，将新的头节点的prev指针设置为undefined
                }
            } else if (index === this.count - 1) { // 如果要删除尾节点
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = undefined; // 将前一个节点的next指针设置为undefined
            } else { // 否则，在链表中间删除节点
                current = this.getNodeAt(index);
                const previous = current.prev;
                previous.next = current.next;
                current.next.prev = previous; // 新增prev指针，连接前一个节点和后一个节点
            }
            this.count--; // 链表长度减1
            return current.element; // 返回删除的节点元素值
        }
        return undefined; // 索引越界，返回undefined
    }

    // 返回头节点
    getHead() {
        return this.head;
    }

    // 返回尾节点
    getTail() {
        return this.tail;
    }
}

五、循环链表

循环链表与单链表的结构相似，只是将链表的首尾相连，即尾结点的指针域为指向头结点的指针，从而形成了一个环状的链表。

// 循环链表类，继承自链表类
class CircularLinkedList extends LinkedList {
    constructor() {
        super(); // 调用父类的构造函数，初始化头节点和链表长度
    }

    // 在链表末尾插入元素
    push(element) {
        const node = new Node(element); // 创建新的节点
        let current;
        if (this.head == null) { // 如果链表为空，将新节点设置为头节点
            this.head = node;
        } else {
            current = this.getNodeAt(this.size() - 1); // 找到最后一个节点
            current.next = node; // 将最后一个节点的next指针指向新节点
        }
        node.next = this.head; // 将新节点的next指针指向头节点，形成循环链表
        this.count++; // 链表长度加1
    }

    // 在指定位置插入节点
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new Node(element); // 创建新的节点
            let current = this.head;
            if (index === 0) { // 如果要插入到头节点位置
                if (this.head == null) { // 如果链表为空，将新节点设置为头节点，并将其next指针指向自己
                    this.head = node;
                    node.next = this.head;
                } else {
                    node.next = current; // 将新节点的next指针指向当前头节点
                    current = this.getNodeAt(this.size() - 1); // 找到最后一个节点
                    this.head = node; // 更新头节点指针
                    current.next = this.head; // 将最后一个节点的next指针指向新的头节点
                }
            } else {
                const previous = this.getNodeAt(index - 1); // 找到要插入位置的前一个节点
                node.next = previous.next; // 将新节点的next指针指向前一个节点的next指针指向的节点
                previous.next = node; // 将前一个节点的next指针指向新节点
            }
            this.count++; // 链表长度加1
            return true;
        }
        return false;
    }

    // 根据索引删除节点
    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index === 0) { // 如果要删除头节点
                if (this.size() === 1) { // 如果链表只有一个节点，将头节点设置为undefined
                    this.head = undefined;
                } else {
                    let last = this.getNodeAt(this.size() - 1); // 找到最后一个节点
                    this.head = this.head.next; // 将头节点指向下一个节点
                    last.next = this.head; // 将最后一个节点的next指针指向新的头节点
                }
            } else {
                const previous = this.getNodeAt(index - 1); // 找到要删除节点的前一个节点
                current = previous.next; // 找到要删除的节点
                previous.next = current.next; // 将前一个节点的next指针指向要删除节点的next指针指向的节点
            }
            this.count--; // 链表长度减1
            return current.element; // 返回删除的节点元素值
        }
        return undefined; // 索引越界，返回undefined
    }
}

循环链表与普通链表最大的区别在于循环链表的最后一个节点的next指针指向头节点，形成了一个闭环。这样就可以通过头节点遍历整个链表，同时在插入和删除操作中要特别注意更新头节点以及最后一个节点的next指针。