JS实现数据结构-链表

Posted on | Edited on | In

什么是链表

链表是最基础的一种数据结构, 根据Wiki上的解释:

链表 是一种常见的基础数据结构, 是一种线性表, 但是并不会按线性的顺序存储数据, 而是在每一个节点里存到下一个节点的指针.

在JS中简单地说, 有一个对象, 它有一个属性存储数据值, 另一个属性存储其它的对象, 组成的一种数据结构.

单向链表

单向链表

根据链表的定义, 下面用JS实现单向链表数据结构的初始化定义

1
2
3
4
5
6
7
8
9
10
11
12
13
// 定义节点
function Node(data) {
  this.data = data;
  this.next = null;
}

// 定义单向链表
function SingleLinkedList() {
  this.head = null;  // 指向第一个节点
  this.tail = null;  // 指向最后一个节点

  this.length = 0;
}

插入节点

因为SingleLinkedList中有指向第一个和指向最后一个的指针, 在进行插入节点通过控制head和tail的指向, 例如在链表头部插入节点, 先将新的节点node的next指向链表的头节点, 也就是head, 再修改head的指向到新的头节点node, 需要注意的是当SingleLinkedList是初始化的空链表, head和tail都指向null

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
// 头部插入节点
SingleLinkedList.prototype.insertHead = function(data) {
  var node = new Node(data);  // 节点Node实例

  if (this.head === null) {  // 空链表
    this.head = node;
    this.tail = node;
  } else {
    node.next = this.head;
    this.head = node;
  }

  this.length++;
};

//　尾部插入节点
SingleLinkedList.prototype.insertTail = function(data) {
  var node = new Node(data);

  if (this.tail === null) {  // 空链表
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    this.tail = node;
  }

  this.length++;
};

删除节点

删除节点也是通过head和tail的指向实现功能, 例如删除头节点, 最初head的指向为头节点, 通过修改head指向下一个节点的操作, 来达到删除头节点的效果

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
// 删除头部节点
SingleLinkedList.prototype.deleteHead = function() {
  this.head = this.head.next;
  this.length--;

  return "Delete head node";
};

// 删除尾部节点
SingleLinkedList.prototype.deleteTail = function() {
  var currentNode = this.head;

  if (currentNode.next === null) {  // 链表只有一个节点
    this.head = null;
    this.tail = null;
  } else {
    while(currentNode.next.next !== null) {
      currentNode = currentNode.next;
    }

    currentNode.next = null;
    this.tail = currentNode;
  }
  
  this.length--;
};

双向链表

双向链表的结构跟单向链表差不多, 有区别的是在双向链表中, 每个节点有存储数据的属性, 指向前驱节点的指针, 指向后驱节点的指针, 头节点的前驱指向null, 尾节点的后驱指向null

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
// 定义节点
function Node(data) {
  this.data = data;
  this.previous = null;
  this.next = null;
}

// 定义双向链表
function DoubleLinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

插入节点

双向链表的插入节点需要注意两点:

  • 头部插入节点, 前驱指针指向新节点
  • 尾部插入节点, 新节点的前驱指向旧链表的最后一个节点
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
// 头部插入节点
DoubleLinkedList.prototype.insertHead = function(data) {
  var node = new Node(data);

  if (this.head === null) {  // 空链表
    this.head = node;
    this.tail = node;
  } else {
    node.next = this.head;  // 新节点的后驱指向链表第一个节点
    this.head.previous = node;  // 第一个节点的前驱指向新节点
    this.head = node;  // 链表head修改指向新节点
  }
  
  this.length++;
};

// 尾部插入节点
DoubleLinkedList.prototype.insertTail = function(data) {
  var node = new Node(data);

  if (this.tail === null) {  // 空链表
    this.head = node;
    this.tail = node;
  } else {
    node.previous = this.tail;  // 新节点的前驱指向链表的最后一个节点
    this.tail.next = node;  // 最后一个节点后驱指向新节点
    this.tail = node;  // 链表tail修改指向新节点
  }

  this.length++;
};

删除节点

双向链表的删除节点与单向链表的差不多, 区别是删除头节点时, 注意新的头部节点的前驱应该要指向null

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
// 删除头部节点
DoubleLinkedList.prototype.deleteHead = function() {
  if (this.head.next === null) {  // 只有一个节点
    this.head = null;
    this.tail = null;
  } else {
    this.head = this.head.next;  // 链表head指向第二个节点
    this.head.previous = null;  // 第二个节点的前驱指向null
  }

  this.length--;
};

// 删除尾部节点
DoubleLinkedList.prototype.deleteTail = function() {
  var currentNode = this.head;

  if (this.head.next === null) {  // 只有一个节点
    this.head = null;
    this.tail = null;
  } else {
    while(currentNode.next.next !== null) {
      currentNode = currentNode.next;
    }
    currentNode.next = null;
    this.tail = currentNode;
  }

  this.length--;
};