链表

在内存中，数组是连续的，不间断的。如果从数组中间插入或者删除一个元素需要移动元素。
链表和数组不同，链表中的元素在内存中不是连续的，每个元素由一个存储元素本身的节点和指向下一个元素的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    val:1,
    next:{
        val:2,
        next:{
            val:3,
            next:{
                val:4,
                next:undefined
            }
        }
    }
}

工具函数

创建一个节点

1
2
3
4
5
6
7
8
9
class Node {
    constructora(val){
        this.val = val
        this.next = undefined
    }
}
// 通过new Node可以初始化一个节点
let node = new Node()
node.val = 10

判断两个元素是否相等

1
2
3
function defaultEquals(a, b) {
    return a === b
  }

链表

创建链表

1
2
3
4
5
6
7
8
class linkedList {
    constructor(equalsFn = defaultEquals) {
      this.count = 0
      this.head = undefined
      this.equalsFn = equalsFn
    }
}

向链表尾部添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
push(element) {
  const node = new Node(element)
  let current
  // 当前链表为空，直接赋值
  if (!this.head) {
    this.head = node
  } else {
    // 遍历节点找到最后一个节点，将next设置为node
    current = this.head
    while(current.next !== null){
      current = current.next
    }
    current.next = node
  }
  this.count++
}
// 测试push方法
const list = new linkedList()
list.push(10)
list.push(60)
console.log(list)

从链表中移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
remove(index){
  // 头部删除直接将head.next指向
  if (index >= 0 && index <= this.count) {
    let current = this.head
    if (index === 0) {
      this.head = current.next
    } else {
      const prev = this.getElementAt(index-1)
      current = prev.next
      prev.next = current.next
    }
    this.count--
    return current
  }
  return undefined
}
 // 测试remove方法
  const list = new linkedList()
  list.push(10)
  list.push(60)
  list.push(100)
  console.log(list.remove(1))

迭代循环链表到目标位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
getElementAt(index){
  //  找到index的位置
  if (index >= 0 && index <= this.count) {
    let node = this.head
    for (let i = 0; i < index && node !== null; i++) {
      node = node.next
    }
    return node
  }
  return undefined
}

  // 测试getElementAt方法
  const list = new linkedList()
  list.push(10)
  list.push(60)
  list.push(100)
  console.log(list.getElementAt(1))

任意位置插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
insert(element,index) {
      if(index >= 0 && index <= this.count) {
        let node = new Node(element)
        if (index === 0) {
          let current = this.head
          node.next = current
          this.head = node
        } else {
          const prev = this.getElementAt(index-1)
          node.next = prev.next
          prev.next= node
        }
        this.count++
        return true
      }
      return false
    }
  //测试insert方法
  const list = new linkedList()
  list.push(10)
  list.push(60)
  list.push(100)
  list.insert(888,0)
  console.log(list)

返回一个元素的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
indexOf(element) {
      let current = this.head
      for (let i = 0; i < this.count; i++) {
        if (current.val === element) {
          return i
        }
        current = current.next
      }
      return -1
    }
//测试indexOf方法
  const list = new linkedList()
  list.push(10)
  list.push(60)
  list.push(100)
  console.log(list.indexOf(100))

双向链表

创建链表

这里可以继承扩展Node类型

1
2
3
4
5
6
7
class DoubleNode extends Node {
    constructor(element,next,prev) {
      super(element,next)
      this.prev = prev // 新增，用来保存前一个节点的引用
    }
}

1
2
3
4
5
6
7
class DoublyLinkedList extends linkedList {
    constructor() {
      super()
      this.tail = undefined // 新增加的，用来保存最后一个节点的引用
    }
}

任意位置插入元素

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
insert(element,index) {
  if (index >= 0 && index <= this.count) {
    let current = this.head
    let node = new DoubleNode(element)
    if (index === 0) {
      if (!this.head) {
        this.head = node
        this.tail = node
      } else {
        node.next = current
        current.prev = node
        this.head = node
      }
    } else if (index === this.count) {
      // 末尾节点
      current = this.tail
      current.next = node
      node.prev = current
      this.tail = node
    } else {
      // 中间节点
      let prev = this.getElementAt(index-1)
      current = prev.next
      node.next = current
      prev.next = node
      current.prev = node
      node.prev = prev
    }
    this.count++
    return true
  }
  return false
}

从任意位置移除元素

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
removeAt(index) {
  if (index >= 0 && index <= this.count) {
    let current = this.head
    if (index === 0) {
      this.head = current.next
      if (this.count === 1){
        this.tail = undefined
      } else {
        this.head.prev = undefined
      }
    } else if (index === this.count - 1) {
      current = this.tail
      // debugger
      this.tail = current.prev
      this.tail.next = undefined
    }
  }

}

  const list = new DoublyLinkedList()
  list.push(1)
  list.push(3)
  list.push(4)
  list.push(8)
  list.removeAt(3)
  console.log(list)

末尾添加元素

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
push(element) {
  const node = new Node(element)
  let current
  // 当前链表为空，直接赋值
  if (!this.head) {
    this.head = node
    this.head.prev = undefined
  } else {
    // 遍历节点找到最后一个节点，将next设置为node
    current = this.head
    while(current.next !== null){
      let prev = current
      current = current.next
      current.prev = prev
    }
    current.next = node
    node.prev = current
    this.tail = node
  }
  this.count++
}

  const list = new DoublyLinkedList()
  list.push(1)
  list.push(3)
  list.push(4)
  list.push(8)
  list.removeAt(3)
  console.log(list)

循环链表

循环链表，头尾相接

创建链表

1
2
3
4
5
6
7
class linkedList {
    constructor(equalsFn = defaultEquals) {
      this.count = 0
      this.head = undefined
      this.equalsFn = equalsFn
    }
}

任意位置插入元素

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
insert(element,index) {
     if (index >= 0 && index <= this.count) {
       let current = this.head
       let node = new DoubleNode(element)
       if (index === 0) {
         if (!this.head) {
           this.head = node
           this.tail = node
           node.next = this.head
         } else {
           node.next = current
           current = this.getElementAt(this.size())
           current.prev = node
           this.head = node
           current.next = this.head
         }
       } else if (index === this.count) {
         // 末尾节点
         current = this.tail
         current.next = node
         node.prev = current
         this.tail = node
       } else {
         // 中间节点
         let prev = this.getElementAt(index-1)
         current = prev.next
         node.next = current
         prev.next = node
         current.prev = node
         node.prev = prev
       }
       this.count++
       return true
     }
     return false
   }

从任意位置移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
removeAt(index) {
  if (index >= 0 && index <= this.count) {
    let current = this.head
    if(index === 0) {
      if (this.size() === 1) {
        this.head = undefined
      } else {
        const removed = this.head
        this.head = this.head.next
        current = this.getElementAt(this.size())
        current.next = this.head
        current = removed
      }
    } else {
      const prev = this.getElementAt(index-1)
      current = prev.next
      prev.next = current.next
    }
    this.count--
    return current.element
  }
  return undefined
}

链表实现堆栈

创建类

1
2
3
4
5
6
class StackLinkedList {
  constructor () {
    this.items = new DoublyLinkedList()
  }


尾部添加

1
2
3
4
5
push(element) {
  // 尾部添加
  this.item.push(element)
}

尾部删除

1
2
3
4
5
6
7
pop () {
  if (this.isEmpty()) {
    return undefined
  }
  return this.items.removeAt(this.size()-1)
}

获取队列中第一个元素

1
2
3
4
5
6
7
8
peek() {
  // 获取队列中第一个元素，链表就是最后一个节点
  if (this.isEmpty()) {
    return undefined
  }
  return this.items.getElementAt(this.size()-1).element
}

其他

1
2
3
4
5
6
7
8
9
10
11
12
isEmpty() {
  return this.items.isEmpty()
}
  
size() {
  return this.item.size()
}
  
clear() {
  return this.items.clear()
}

  • 在分析链表问题时候，不要考虑互相引用问题，current就是当前单一个节点，prev就是上一个单个节点
  • 只要有涉及不断a = a.next，就必须申明一个来保存这个节点，let b = a,用b = b.next代替，最后返回a
  • 链表处理时候，先链接后面的节点