首页 数据结构

# 链表

❑ push (element)：向链表尾部添加一个新元素。
❑ insert (element, position)：向链表的特定位置插入一个新元素。
❑ getElementAt (index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回 undefined。
❑ remove (element)：从链表中移除一个元素。
❑ indexOf (element)：返回元素在链表中的索引。如果链表中没有该元素则返回 - 1。
❑ removeAt (position)：从链表的特定位置移除一个元素。
❑ isEmpty ()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
❑ size ()：返回链表包含的元素个数，与数组的 length 属性类似。
❑ toString ()：返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//先定义节点类
class Node {
    constructor(data) {
        this.value = data
        this.next = null
    }
}

// 定义链表
class LinkedList {
    head = null
    count = 0

    // 1.添加节点
    push(element) {
        let node = new Node(element)
        //判断是否为空
        if (this.head === null) {
            //链表为空 新加的节点就是头
            this.head = node
        } else {
            let current = this.head
            while (current.next) {       //while循环到最后一个节点
                current = current.next
            }
            current.next = node
        }
        this.count++
    }
    // 2.删除指定位置的节点: xyz x.next = y.next 删除y
    removeAt(position) {
        if (position >= 0 && position < this.count) {
            let current = this.head
            if (position === 0) {
                this.head = this.head.next
            } else {
                let previous = null
                for (let i = 0; i < position; i++) {
                    previous = current        //不断往右移动
                    current = current.next
                }
                previous.next = current.next
                current.next = null
            }
            this.count--
            return current
        }
        return;
    }
    // 3.在指定位置插入一个节点
    insert(element, position) {
        if(position<0||position>this.count) return false
        let node = new Node(element)
        if (position === 0) {
            node.next = this.head
            this.head = node
        }else if(position === this.count){
            this.push(element)
        }else{
            let previous = this.head
            for(let i =0;i<position-1;i++){
                previous = previous.next
            }
            node.next = previous.next
            previous.next = node
        }
        this.count++
        return true
    }
    // 4.获取指定位置的节点
    getElementAt(index){
        if(index<0 || index>this.count) return undefined
        else{
            let current = this.head
            for(let i=0;i<index-1;i++){
                current = current.next
            }
            return current.value
        }
    }
    // 5.返回某个节点的下标
    indexOf(element){
        let current = this.head
        for(let i=0;i<this.count;i++){
            if(this.isEqual(current.value,element)){
                return i
            }
            current = current.next
        }
        return -1
    }
    // ** 封装一个递归判断相等的函数 这里暂时先用JSON.stringify **
    isEqual(a,b){
        return JSON.stringify(a)===JSON.stringify(b)
    }
    // 6.从链表中删除一个元素
    remove(element){
        const index = this.indexOf(element)
        return removeAt(index)
    }
    // 7.获取链表的大小
    size(){
        return this.count
    }
    // 8.判断是否为空
    isEmpty(){
        return this.count===0
    }
    // 9.重写toString方法输出所有值
    toString(){
        let str = ''
        let current = this.head
        for(let i=0;i<this.count;i++){
            str+=String(current.value)
            current = current.next
        }
        return str
    }
}

试一下

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
const linkedlist = new LinkedList()

linkedlist.push('A')
linkedlist.push('B')
linkedlist.push('C')
linkedlist.push('D')
linkedlist.insert('E',2)

console.log(linkedlist)
console.log(linkedlist.getElementAt(3))
console.log(linkedlist.getElementAt(5))
console.log(linkedlist.toString())
/{
  "head": {
    "value": "A",
    "next": {
      "value": "B",
      "next": {
        "value": "E",
        "next": {
          "value": "C",
          "next": {
            "value": "D",
            "next": null
          }
        }
      }
    }
  },
  "count": 5
}
"E"
"D"
"ABECD"
*/