链表

算法 / 数据结构
字数统计: 1.6k   |   阅读时长≈ 7 分钟

单向链表

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
class CreateNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    // 内部使用头节点便于控制
    this._head = { next: null };
    // 对外头节点
    this.count = 0;
  }
  push(node) {
    let cur = this._head;
    // 找到链表中的最后一个
    while (cur.next !== null) {
      cur = cur.next;
    }
    this.count += 1;
    cur.next = node;
  }
  // 把指定位置元素移除
  removeAt(index) {
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    let res = null;
    let count = 0;
    // 拿到目标节点的前一个节点
    while (index !== count) {
      cur = cur.next;
      count++;
    }
    // 保存目标节点
    res = cur.next;
    // 拼接后面的节点
    cur.next = cur.next.next;
    this.count -= 1;

    return res;
  }
  // 查找指定位置元素
  getItem(index) {
    let count = 0;
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    while (count !== index) {
      cur = cur.next;
      count++;
    }
    return cur.next;
  }
  // 在任意位置插入元素
  insert(index, node) {
    // 边界处理,因为可以在最有一个节点之后插入,所以不需要判断index和长度项等的情况
    if (index < 0 || index > this.count) return;
    //插入元素是在指定位置元素的前面插入
    let cur = this._head;
    let count = 0;
    // 找到插入位置的节点,把新节点链接到当前节点
    while (index !== count) {
      cur = cur.next;
      count += 1;
    }
    // 保存下一个节点
    const next = cur.next;
    cur.next = node;
    node.next = next;
    this.count += 1;

  }
  // 返回一个元素的位置
  indexOf(node) {
    let count = 0;
    let cur = this.head;
    while (cur !== null) {
      if (node === cur) return count;
      cur = cur.next;
      count += 1;
    }
    return -1;
  }
  // 移除某个元素
  remove(node) {
    const index = this.insert(node);
    return this.removeAt(index);
  }
  // 获取头节点
  getHead() {
    return this._head.next;
  }
}

const list = new LinkedList();
list.push(new CreateNode(1))
list.push(new CreateNode(2))
list.push(new CreateNode(3))
list.insert(3, new CreateNode(4))
console.log(list.getHead())

双向链表

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
class CreateNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    // 添加头节点信息
    this._head = {
      next: null,
      prev: null
    };
    this.count = 0;
  }
  push(node) {
    let cur = this._head;
    // 找到链表中的最后一个
    while (cur.next !== null) {
      cur = cur.next;
    }
    // 没有初始化头节点的时候不需要指明prev
    if (this._head.next !== null) {
      node.prev = cur;
    }
    cur.next = node;
    this.count += 1;
    return this.count;
  }
  // 把指定位置元素移除
  removeAt(index) {
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    let res = null;
    let count = 0;
    // 拿到目标节点的前一个节点
    while (index !== count) {
      cur = cur.next;
      count++;
    }
    // 保存需要返回的目标节点
    res = cur.next;
    // 移除之后要修复后一个节点的prev指针
    // 需要把修复prev的操作放在前面,因为下一步保存的时候仍然保留了,后一个节点的错误引用
    cur.next.next.prev = cur
    // 拼接后面的节点
    cur.next = cur.next.next;
    this.count -= 1;

    return res;
  }
  // 查找指定位置元素
  getItem(index) {
    let count = 0;
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    while (count !== index) {
      cur = cur.next;
      count++;
    }
    return cur.next;
  }
  // 在任意位置插入元素
  insert(index, node) {
    // 边界处理,因为可以在最有一个节点之后插入,所以不需要判断index和长度项等的情况
    if (index < 0 || index > this.count) return;
    //插入元素是在指定位置元素的前面插入
    let cur = this._head;
    let count = 0;
    // 找到插入位置的节点,把新节点链接到当前节点
    while (index !== count) {
      cur = cur.next;
      count += 1;
    }
    // 对节点的引用应该是先修复指针,在赋值
    // 保存下一个节点
    const next = cur.next;
    // 下一个节点的prev;
    next.prev = node;
    // 新节点的next
    node.next = next;
    // 新节点的prev
    node.prev = cur;
    // 前一个节点的next
    cur.next = node;
    this.count += 1;
  }
  // 返回一个元素的位置
  indexOf(node) {
    let count = 0;
    let cur = this.head;
    while (cur !== null) {
      if (node === cur) return count;
      cur = cur.next;
      count += 1;
    }
    return -1;
  }
  // 移除某个元素
  remove(node) {
    const index = this.insert(node);
    return this.removeAt(index);
  }
  // 获取头节点
  getHead() {
    return this._head.next;
  }
}

循环链表

和前面两种链表相比,循环链表需要拿到,返回的那个头节点,用于判断是否是最后一个节点

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
120
121
122
123
124
125
class CreateNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class CircularLinkedList {
  constructor() {
    this._head = {
      next: null,
    };
    this.count = 0;
  }
  push(node) {
    let cur = null;
    // 没有初始化头节点则
    if (this.getHead() == null) {
      cur = this._head;
      // 最有一个节点指向自己
      node.next = node;
    } else {
      // 如果已经有了头节点,保存头节点用于修复指针
      const head = this.getHead();
      cur = head;
      while (cur.next !== head) {
        cur = cur.next;
      }
      node.next = head;
    }
    cur.next = node;
    this.count += 1;
    return this.count;
  }
  // 把指定位置元素移除
  removeAt(index) {
    if (index < 0 || index >= this.count) return undefined;
    // 保存下真实的头节点
    const head = this.getHead()
    let cur = this._head;
    let res = null;
    let count = 0;
    // 拿到目标节点的前一个节点
    while (index !== count) {
      cur = cur.next;
      count++;
    }

    // 保存需要返回的目标节点
    res = cur.next;
    // 如果是头节点
    if (index === 0) {
      // 拿到最后一个节点,修复next指针
      const tail = this.getItem(this.count - 1);
      tail.next = cur.next.next;
      cur.next = cur.next.next;
    }
    // 如果被移除的节点是最后一个节点
    else if (index === this.count - 1) {
      cur.next = head;
    } else {
      cur.next = cur.next.next;
    }
    this.count -= 1;

    return res;
  }
  // 查找指定位置元素
  getItem(index) {
    let count = 0;
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    while (count !== index) {
      cur = cur.next;
      count++;
    }
    return cur.next;
  }
  // 在任意位置插入元素
  insert(index, node) {
    // 边界处理,因为可以在最有一个节点之后插入,所以不需要判断index和长度项等的情况
    if (index < 0 || index > this.count) return;
    //插入元素是在指定位置元素的前面插入
    const head = this.getHead();
    let cur = this._head;
    let count = 0;
    // 找到插入位置的节点,把新节点链接到当前节点
    while (index !== count) {
      cur = cur.next;
      count += 1;
    }
    // 末尾插入要修复next
    if (index === this.count - 1) {
      node.next = head;
    }
    // 头部插入
    if (index === 0) {
      const tail = this.getItem(this.count - 1);
      tail.next = node;
    }
    const next = cur.next;
    cur.next = node;
    node.next = next;
    this.count += 1;
  }
  // 返回一个元素的位置
  indexOf(node) {
    let count = 0;
    let cur = this.head;
    while (count < this.count) {
      if (node === cur) return count;
      cur = cur.next;
      count += 1;
    }
    return -1;
  }
  // 移除某个元素
  remove(node) {
    const index = this.insert(node);
    return this.removeAt(index);
  }
  // 获取头节点
  getHead() {
    return this._head.next;
  }
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2025 SunZhiqi

此时无声胜有声！

支付宝
微信