用JS实现一个单链表和常用操作方法

发表于

链表

用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。

  • 需要遍历才能查询到元素，查询慢。
  • 插入元素只需断开连接重新赋值，插入快。

构造函数

链表的元素都是节点，首先要构建一个节点Node类，每个节点都是Node的实例。
Node类有两个属性，一个是节点的值，一个是对下一个节点的指向（next）。
链表需要一个头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Node{
    constructor(element){
        this.element = element;
        this.next = null;
    }
}
class LinkList{
    //构造出head节点
    constructor(){
        this.head = new Node('head');
    }
}

添加方法

  1. 尾部添加节点
    添加节点非常简单，从头节点开始，用next属性做遍历，当某个节点的next属性为null，则说明到达尾部，将尾部节点的next指向要添加的节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //添加节点
    append(newVal){
        let newNode = new Node(newVal);
        //从头结点开始走
        let currentNode = this.head;
        //结点next不为null，可往后走
        while(currentNode.next!=null){
            currentNode = currentNode.next
        }
        currentNode.next = newNode;
    }

  2. 根据节点值查找节点
    链表和数组不同，并没有indexOf方法，只能逐个遍历判断。
    由于头节点没有值，将从头节点后的第一个节点开始进行。
    循环条件：节点不为空且节点值和目标值不等，则循环下一个节点。
    循环完毕没找到节点，返回-1

    1
    2
    3
    4
    5
    6
    7
    8
    //根据节点值查找节点
    findByValue(item){
        let currentNode = this.head.next;
        while(currentNode != null && currentNode.element != item){
            currentNode = currentNode.next;
        }
        return currentNode===null? -1 : currentNode
    }

  3. 根据索引值获取节点
    链表和数组不同，内存地址不连续，无法直接通过索引下标（链表根本不存在下标的概念）查找。
    头节点之后的节点是索引0号节点，用pos变量来记录节点的索引，来和传入的index值作比较。
    循环条件：节点不为空且pos和索引值不等，则循环下一个节点。
    循环完毕没找到节点（index超出节点数），返回-1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //根据index索引查找节点，下标从0开始
    findByIndex(index){
        //头节点之后的节点是索引0号节点
        let currentNode = this.head.next;
        let pos = 0;
        while(currentNode != null && pos != index){
            currentNode = currentNode.next;
            pos++
        }
        return currentNode===null ? -1: currentNode
    }

  4. 指定元素向后插入
    通过findByValue方法找到要插入的节点位置，在其后方插入新元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //指定元素向后插入
    insert(newElement, element){
        let currentNode = this.findByValue(element);
        if(currentNode === -1){
            console.log('未找到插入位置')
            return
        }
        let newNode = new Node(newElement)
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }

  5. 删除元素
    删除链表元素的方法很简单，找到要删除的元素，把它上一个节点的next指向它后一个节点即可。
    那么我们需要先写一个方法来找目标节点的前一个节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //查找前一个节点
    findPrev(item){
        let currentNode = this.head;
        while(currentNode.next != null && currentNode.next.element!=item){
            currentNode = currentNode.next
        }
        if(currentNode.next === null){
            return -1
        }
        return currentNode
    }

之后只要让把prevNode.next指向prevNode.next.next就完成了删除。

1
2
3
4
5
6
7
8
remove(item){
    let prevNode = this.findPrev(item)
    if(prevNode===-1){
        console.log('未找到元素')
        return
    }
    prevNode.next = prevNode.next.next
}

完整代码

为了方便测试，需要写一个打印链表元素的方法。非常简单，从头节点后的节点开始遍历，将节点的element打印出来。

1
2
3
4
5
6
7
8
9
10
//展示链表
display(){
    let currentNode = this.head.next;
    let linkedListElementChain = [];
    while(currentNode!=null){
        linkedListElementChain.push(currentNode.element)
        currentNode = currentNode.next;
    }
    console.log(linkedListElementChain.join('  ->  '))
}

完整示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Node{
    constructor(element){
        this.element = element;
        this.next = null;
    }
}
class LinkList{
    //构造出head节点
    constructor(){
        this.head = new Node('head');
    }
    //添加节点
    append(newVal){
        let newNode = new Node(newVal);
        //从头结点开始走
        let currentNode = this.head;
        //结点next不为null，可往后走
        while(currentNode.next!=null){
            currentNode = currentNode.next
        }
        currentNode.next = newNode;
    }
    //根据value查找节点
    findByValue(item){
        let currentNode = this.head.next;
        while(currentNode != null && currentNode.element != item){
            currentNode = currentNode.next;
        }
        return currentNode===null? -1 : currentNode
    }
    //根据index索引查找节点，下标从0开始
    findByIndex(index){
        //头节点之后的节点是索引0号节点
        let currentNode = this.head.next;
        let pos = 0;
        while(currentNode != null && pos != index){
            currentNode = currentNode.next;
            pos++
        }
        return currentNode===null ? -1: currentNode
    }
    //指定元素向后插入
    insert(newElement, element){
        let currentNode = this.findByValue(element);
        if(currentNode === -1){
            console.log('未找到插入位置')
            return
        }
        let newNode = new Node(newElement)
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }
    //查找前一个
    findPrev(item){
        let currentNode = this.head;
        while(currentNode.next != null && currentNode.next.element!=item){
            currentNode = currentNode.next
        }
        if(currentNode.next === null){
            return -1
        }
        return currentNode
    }
    //根据值做删除
    remove(item){
        let prevNode = this.findPrev(item)
        if(prevNode===-1){
            console.log('未找到元素')
            return
        }
        prevNode.next = prevNode.next.next
    }
    //展示链表
    display(){
        let currentNode = this.head.next;
        let linkedListElementChain = [];
        while(currentNode!=null){
            linkedListElementChain.push(currentNode.element)
            currentNode = currentNode.next;
        }
        console.log(linkedListElementChain.join('  ->  '))
    }
}
const LList = new LinkList();
LList.append('1');
LList.append('2');
LList.append('3');
LList.display();  // 1 -> 2 -> 3
LList.insert('0', '1') 
LList.remove('3')
LList.display(); // 1 -> 0 -> 2

Snapline wechat
扫码关注我的公众号“约翰柠檬的唱片店”
Buy me a cup of Coffee