前端也需要了解的数据结构-链表

最近被小伙伴问到链表是什么,链表作为一种常见的数据结构,但是很多前端coder对此并不了解,写下这篇文章,介绍下链表的js实现,不了解链表的同学也可以做个参考

单向链表

• 和数组区别，地址离散。它在内存地址中可以离散的分配，由于它是离散的分配，所以他可以省去很多的麻烦，不像数组由于预留空间不足经常需要拷贝，分配新的内存地址
• 总体上还是线性的数据，属于链式的排列

程序表示

· 表示一个节点node ···js function ListNode(key){ // 节点就单纯是一个数据结构,不需要其他方法 this.key = key; // 传入的key this.next = null; // 初始化时,下一个节点指向null }

- 表示单向链表
```js
class LinkedList { // 使用class,可以添加其他方法
constructor(){
this.head = null; // 初始化时,头指针指向null
}
}
复制代码

向空链表中插入元素

1. 创建一个空链表,HEAD指针指向NULL

const list = new LinkedList()
复制代码

2. 创建一个包含数据1的节点

const node = new ListNode(1)
复制代码

3. 将HEAD指针指向节点

list.head = node;
复制代码

4. 当前链表结构

LinkedList {
head: ListNode {
key: 1,
next: null
}
}
复制代码

5. 再插入一个元素2

• 再创建一个包含数据2的节点

const node2 = new ListNode(2)
复制代码

• 将节点2的next指针指向节点1

node2.next = node;
复制代码

• 调整HEAD指针指向节点2

list.head = node2;
复制代码

• 当前链表结构

LinkedList {
head: ListNode {
key: 2,
next: ListNode {
key: 1,
next: null
}
}
}
复制代码

插入的完整程序 (时间复杂度O(1))

当头指针不为null时,新插入的节点的next指针首先指向头指针指向的节点,然后将头指针指向插入的节点

class LinkedList {
    constructor(){
         this.head = null;
    }
    insert(node){
        if(this.head !== null){
            node.next = this.head
        }
        this.head = node;
    }
}
复制代码

在链表中查找节点(时间复杂度O(n))

class LinkedList {
...
find(node){
let p = this.head; // 创建一个遍历指针
while(p && p !== node){ // 当p为null或者p为node时,停止遍历
p = p.next;
}
return p; // 如果node在链表中, p = node,否则返回null
}
}
复制代码

已知节点2,删除节点2

1. 找到节点2之前的节点prev 这是一个O(n)的操作

prev.next = node2.next;
复制代码

双向链表图示

双向链表(Double Linked-List)

• 追加(append/push) - O(1)
• 索引 访问/修改 (A[idx] = ...) - O(n)
• 插入 (insert) - O(1)
• 删除 (delete/remove) - O(1)
• 合并 (merge/concat) - O(1)

从api上看,链表比数组 在索引上变慢了,但是在插入、删除、合并上都变快了

双向链表程序

• 表示一个链表节点

function ListNode(key){
this.key = key;
this.prev = null;
this.next= null;
}
复制代码

• 表示双向链表

class DoubleLinkedList {
constructor(){
this.head = null;
}
}
复制代码

双向链表删除元素2 (时间复杂度O(1))

节点2的前一个节点(节点1)的next指针指向节点2的下一个节点(节点3)

node2.prev.next = node2.next
复制代码

节点2的下一个节点(节点2)的prev指针指向节点2的上一个节点(节点1)

node2.next.prev = node2.prev;
复制代码

删除节点2的指针,减少引用计数

delete node2.next;
delete node2.prev
复制代码

双向链表的插入 - O(1)

insert(node) {
    if(!(node instanceof ListNode)){
        node = new ListNode(node);
    }
    if (this.tail === null) {
        this.tail = node;
    }
    if (this.head !== null) {
        this.head.prev = node;
        node.next = this.head;
    }
    this.head = node;
}
复制代码

双向链表的合并 - O(m+n)

为了让合并操作可以在O(1)完成，除了头指针head外，还需要维护一个尾指针tail。

merge(list) {
    this.tail.next = list.head;
    list.head.prev = this.tail;
    this.tail = list.tail;
}
复制代码

打印双向链表

print() {
    let str = '';
    let p = this.head
    while (p !== null) {
        str += p.key + '<->';
        p = p.next;
    }
    console.log(str += 'NULL');
}
复制代码

• 完整代码

class DoubleLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }
    print() {
        let str = '';
        let p = this.head
        while (p !== null) {
            str += p.key + '<->';
            p = p.next;
        }
        console.log(str += 'NULL');
    }
    insert(node) {
        if(!(node instanceof ListNode)){
            node = new ListNode(node);
        }
        if (this.tail === null) {
            this.tail = node;
        }
        if (this.head !== null) {
            this.head.prev = node;
            node.next = this.head;
        }
        this.head = node;
    }
    merge(list) {
        this.tail.next = list.head;
        list.head.prev = this.tail;
        this.tail = list.tail;
    }

}
class ListNode {
    constructor(key) {
        this.prev = null
        this.next = null
        this.key = key
    }
}
const list = new DoubleLinkedList()
list.print()
// 输出: NULL
for (let i = 0; i < 5; i++) {
    list.insert(String.fromCharCode('A'.charCodeAt(0) + i))
}

list.print()
// 输出: E<->D<->C<->B<->A<->NULL

list.insert('X')
list.print()
// 输出: X<->E<->D<->C<->B<->A<->NULL

const list2 = new DoubleLinkedList()
list2.insert('Q')
list2.insert('P')
list2.insert('O')
list2.print()
// 输出 O<->P<->Q<->NULL


list2.merge(list)
list2.print()

// 输出 O<->P<->Q<->X<->E<->D<->C<->B<->A<->NULL
复制代码

扩展方法

在链表的使用中,经常要用到一些方法,让我们来实现它吧

• 翻转单向链表

class List {
    ...
    reverse(p = this.head){
        if(p.next){
            reverse(p.next);
            p.next.next = p;
            p.next = null
        }else{
            this.head = p;
        }
    }
}
复制代码

• 写一个函数 center(list) 找到一个链表的中间节点。 如果链表有基数个节点，那么返回中心节点。 如果链表有偶数个节点，返回中间偏左的节点。

// 解法一: 空间复杂度高 O(n) 时间复杂度O(n)
const center = (list)=>{
    let p = list.head
    const arr = []
    while(p){
        arr.push(p)
        p = p.next;
    }
    return arr.length % 2 ? arr[~~(arr.length/2)] : arr[arr.length/2-1]
}
// 解法二 时间复杂度O(n)
const center = (list)=>{
    let p = list.head
    if(p==null) return null
    let count = 0
    while(p){
        count++;
        p = p.next;
    }
    count = count % 2 ? ~~(count/2) : count/2-1
    p = list.head;
    while(count){
        count--
        p = p.next;
    }
    return p
}


// 解法三
function center(list) {
    let fast = list.head,  // 快指针，每次移动两个
        slow = list.head   // 慢指针，每次移动一个
  
    while(fast) {
      fast = fast.next
      fast && (fast = fast.next)
      fast && (fast = fast.next)
      fast && (slow = slow.next)
    }
    return slow
}

const list = new DoubleLinkedList()
console.log(center(list) )// null
list.insert(4)
list.insert(3)
list.insert(2)
list.insert(1)
// list = 1-2-3-4
const node = center(list) // node.key = 2
console.log(node)
list.insert(5)
// list = 5-1-2-3-4
const node2 = center(list) // node.key = 2
console.log(node2)
复制代码