1. 1. 单链表
    1. 1.1. 构造
    2. 1.2. 插入元素
    3. 1.3. 删除元素
    4. 1.4. 逆序构造
    5. 1.5. 链表反转
  2. 2. 循环链表
    1. 2.1. 构造
  3. 3. 双向链表
    1. 3.1. 构造
    2. 3.2. 插入元素
    3. 3.3. 删除元素
【算法】链表操作
算法

单链表

1
2
3
4
5
// 结点结构
function Node (value) {
  this.value = value
  this.next = null
}

构造

输入：[1, 2, 3, 4, 5, 6]

输出：1 -> 2 -> 3 -> 4 -> 5 -> 6

1
2
3
4
5
6
7
8
9
function listConstruct (arr) {
  let res = new Node(null)
  let cur = res
  arr.map(item => {
    cur.next = new Node(item)
    cur = cur.next
  })
  return res.next
}

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function insertNode (list, value, pos) {
  let idx = 0
  let res = new Node(0)
  res.next = list
  let cur = res
  while (idx < pos) {
    idx ++
    cur = cur.next
  }
  let node = new Node(value)
  let temp = cur.next
  cur.next = node
  node.next = temp
  temp = null
  return res.next
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function deleteNode (list, pos) {
  let idx = 0
  let res = new Node(0)
  res.next = list
  let cur = res
  while (idx < pos) {
    idx ++
    cur = cur.next
  }
  let temp = cur.next
  cur.next = temp.next
  temp = null
  return res.next
}

逆序构造

输入：[1, 2, 3, 4, 5, 6]

输出：6 -> 5 -> 4 -> 3 -> 2 -> 1

1
2
3
4
5
6
7
8
9
10
function listConstruct (arr) {
  let cur = null
  let pre = null
  arr.map(item => {
    cur = new Node(item)
    cur.next = pre
    pre = cur
  })
  return pre
}

链表反转

输入：1 -> 2 -> 3 -> 4 -> 5 -> 6

输出：6 -> 5 -> 4 -> 3 -> 2 -> 1

1
2
3
4
5
6
7
8
9
10
11
function reverseList (list) {
  let cur = link
  let pre = null
  while (cur) {
    const temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  return pre
}

循环链表

构造

输入：[1, 2, 3, 4, 5, 6]

输出：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 1

1
2
3
4
5
6
7
8
9
10
function listConstruct (arr) {
  let res = new Node(null)
  let cur = res
  arr.map(item => {
    cur.next = new Node(item)
    cur = cur.next
  })
  cur.next = res.next // 将末尾指向头部
  return res.next
}

双向链表

1
2
3
4
5
6
// 结点结构
function Node (value) {
  this.value = value
  this.next = null
  this.pre = null
}

构造

1
2
3
4
5
6
7
8
9
10
function listConstruct (arr) {
  let res = new Node(null)
  let cur = res
  arr.map((item, index) => {
    cur.next = new Node(item)
    cur.next.pre = index == 0 ? null : cur
    cur = cur.next
  })
  return res.next
}

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function insertNode (list, value, pos) {
  let idx = 0
  let res = new Node(0)
  res.next = list
  let cur = res
  while (idx < pos) {
    idx ++
    cur = cur.next
  }
  let node = new Node(value)
  node.pre = cur
  node.next = cur.next
  cur.next.pre = node
  cur.next = node
  return res.next
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function deleteNode (list, pos) {
  let idx = 0
  let res = new Node(0)
  res.next = list
  let cur = res
  while (idx < pos) {
    idx ++
    cur = cur.next
  }
  cur.pre.next = cur.next
  cur.next.pre = cur.pre
  cur = null
  return res.next
}
Previous post
Next post