链表 - 今天上Code

首页 > 数据结构与算法 > 链表

链表

本文共--字阅读约--分钟 | 浏览: -- Last Updated: 2021-04-27

数组的缺点

数组不总是组织数据的最佳数据结构，原因如下，在很多编程语言中，数组的长度是固定的，当数组已被填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前后向后平移，以反映数组刚刚进行了操作，所有在 JavaScript 中，push 操作比 unshift 插入效率更高，因为 push 不需要移动数组中原有的元素。

JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言的数组相比，效率很低。数组的定义是一段线性分配的内存，它通过整数计算偏移并访问其中的元素。而JavaScript 中，它把数组的下标转换成字符串，用其作为属性，这明显比一个真正的数组慢，但它的优点是使用方便。

var numbers = [1, 2, 3]

var number_object = {
  '0': 1,
  '1': 2,
  '2': 3
}

// 两者类似 都可以这样访问 numbers[0]  number_object[0]
// 不同的是一个继承于 Array.prototype 一个继承于 Object.prototype 拥有着不同的实例方法

测试 push 和 unshift：

function testPush() {
  var a = [];
  console.time('push');
  for (var i = 0; i < 100000; i++) {
    a.push(i)
  }
  console.timeEnd('push');
}

function testUnshift() {
  var a = [];
  console.time('unshift');
  for (var i = 0; i < 100000; i++) {
    a.unshift(i)
  }
  console.timeEnd('unshift');
}

testPush()
testUnshift()

// push: 5.240234375 ms
// unshift: 618.27587890625 ms

如果你发现数组在实际使用时很慢，就可以考虑使用链表来代替它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

定义单向链表

链表是一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫做链。

数组的元素靠它们的位置进行引用，而链表元素则是靠相互之间的关系进行引用。遍历链表，就是跟着链接，从链表的首元素一直走到尾元素（但这不包含链表的头节点，头节点常常用来作为链表的接入点），链表的尾节点指向一个 null 节点。

在链表中插入一个节点的效率很高，只需要修改它前面节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来的前驱指向的节点。

删除一个元素也很简单，将待删除节点的前驱节点指向待删除元素的后继节点，同时将待删除节点指向 null

设计单向链表

// 节点类
function Node(element) {
  this.element = element; // 元素
  this.next = null; // 指针
}

function LinkedList() {
  // 头节点 初始化时头节点的next指针是指向null的 当插入新元素时next会指向新元素
  this.head = new Node("head")
  this.size = 0;
  this.find = find;
  this.insertBefore = insertBefore;
  this.insertAfter = insertAfter;
  this.display = display;
  this.remove = remove;
  this.findPrevious = findPrevious;
  this.append = append;
  this.findLast = findLast;
  this.clear = clear;
  this.pos = 0; // 链表的当前位置
  this.show = show; // 显示当前节点
  this.advance = advance; // 在链表中向前移动n个节点
  this.back = back; // 在链表向后移动n个节点
}

// 遍历链表 查找给定数据 
function find(item) {
  var currNode = this.head;
  while(currNode && currNode.element != item) {
    currNode = currNode.next;
  }
  return currNode;
  // 找到则返回，找不到返回的则是null
  // 因为如果传进来的item 如果等于head那么返回就是head
  // 如果不等于，则循环体至少执行一次，就算只有一个head节点也可以返回null了
}

// 插入新节点
// 在指定的已有子节点之前插入新的子节点。
function insertBefore(newElement, existingItem) {
  // 找到指定节点的前一个节点，在这个前一个节点之后插入新节点
  var anchorItem = this.findPrevious(existingItem)
  if (!anchorItem) {
    return;
  }
  // anchorItem 返回的是Node，所以传给 insertAfter 应该是 anchorItem.element
  this.insertAfter(newElement, anchorItem.element)
}

// 在指定的已有节点之后插入新的字节点
function insertAfter(newElement, existingItem) {
  var anchorItem = this.find(existingItem)
  if (!anchorItem) {
    return false;
  }
  var newNode = new Node(newElement)
  newNode.next = anchorItem.next
  anchorItem.next = newNode
  this.size++
}

// 展示链表
function display() {
  console.log('当前元素数量为: ', this.size);
  if (this.size === 0) {
    return;
  }
  var currNode = this.head;
  while (currNode && currNode.next != null) {
    console.log(currNode.next.element);
    currNode = currNode.next
  }
}

// 寻找给点节点的前一个节点
function findPrevious(item) {
  if (this.size === 0) { // 不为0则链表是有元素的，即head的next是有指向的
    return null
  }
  var currNode = this.head;
  // 检查每一个节点的下一个节点是不是给点节点 不是则继续向下寻找
  while (currNode.next != null && currNode.next.element != item) {
    currNode = currNode.next
  }

  // 循环之后，currNode要么是给定节点的前一个节点要么就是最后一个节点
  if (currNode.next == null) { // 是最后一个节点
    return null
  }

  return currNode
}

// 删除指定节点
function remove(item) {
  var prevNode = this.findPrevious(item)
  if (!prevNode) {
    return;
  }

  if (item === 'head') { // 不能删除头节点
    return;
  }

  if (prevNode.next != null) { // 确定身份
    prevNode.next = prevNode.next.next
    this.size--;
  }
}

// 获取当前链表的最后一个
function findLast() {
  var currNode = this.head;
  while (currNode.next) {
    currNode = currNode.next;
  }
  return currNode;
}

// 向链表尾部添加元素
function append(item) {
  var lastNode = this.findLast()
  var newNode = new Node(item)
  lastNode.next = newNode;
  this.size++;
}

function clear() {
  this.head.next = null;
  this.size = 0;
  this.pos = 0;
}

function show() {
  var currNode = this.head;
  var n = this.pos;
  if (n > this.size) {
    console.log('当前 pos: %s 是一个无效值，已将 pos 重置为 0', n);
    this.pos = 0;
    return;
  }
  while (n-- && currNode.next !== null) {
    currNode = currNode.next;
  }

  console.log('当前节点:', currNode.element);
}

function advance(n) {
  var pos = this.pos;
  pos += n

  if (pos > this.size || pos < 0) {
    console.log('移动无效：超出范围');
    return;
  }
  this.pos = pos;
}

function back(n) {
  var pos = this.pos;
  pos -= n

  if (pos > this.size || pos < 0) {
    console.log('移动无效：超出范围');
    return;
  }
  this.pos = pos;
}

测试代码：

var l = new LinkedList()
l.append('Anna')
l.append('Clayton')
l.display() // Anna Clayton

l.insertBefore('Brown', 'Clayton')
l.display() // Anna Brown Clayton

l.append('David')
l.remove('Clayton')
l.display() // Anna Brown David

l.insertBefore('test', 'Clayton') // 在一个不存在的元素之前插入
l.display() // Anna Brown David

l.insertAfter('Cynthia', 'Brown')
l.display() // Anna Brown Cynthia David

l.show(); // 当前节点: head
l.advance(3)
l.back(1)
l.back(1)
l.show() // 当前节点: Anna

l.back(2) // 移动无效：超出范围

l.show() // 当前节点: Anna

l.clear()
l.display() // 当前元素数量为:  0

双向链表

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单，通过给 Node 对象增加一个属性存储指向前驱节点的链接，这样就容易多了。

双向链表的删除比单向链表的效率更高，因为不需要再查找前驱节点了，首先需要在链表中找出待删除的节点，然后设置该节点的前驱的 next 属性，使其指向待删除节点的后继，再将待删除节点的后继的 previous 指向待删除节点的前驱。

实现代码如下：

function Node(element) {
  this.element = element;
  this.next = null;
  this.previous = null;
}

function TwoWayLinkedList() {
  this.head = new Node('head')
  this.size = 0
  this.find = find;
  this.insertBefore = insertBefore;
  this.insertAfter = insertAfter;
  this.findLast = findLast;
  this.append = append;
  this.display = display;
  this.dispReverse = dispReverse;
  this.remove = remove;
  this.clear = clear;
}

// 查找给定元素，与单向链表一样
function find(item) {
  var currNode = this.head;
  while(currNode && currNode.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}

// 在指定的已有子节点之前插入新的子节点
function insertBefore(newElement, existingItem) {
  var anchorItem = this.find(existingItem);
  if (!anchorItem) {
    return;
  }

  var newNode = new Node(newElement);
  newNode.previous = anchorItem.previous;
  newNode.next = anchorItem;
  anchorItem.previous.next = newNode;
  anchorItem.previous = newNode;
  this.size++;
}

// 在指定的已有节点之后插入新的字节点
function insertAfter(newElement, existingItem) {
  var anchorItem = this.find(existingItem);
  if (!anchorItem) {
    return;
  }

  var newNode = new Node(newElement);
  newNode.previous = anchorItem;
  newNode.next = anchorItem.next;
  if (anchorItem.next) {
    anchorItem.next.previous = newNode;
  }
  anchorItem.next = newNode;
  this.size++;
}

// 查找最后一个元素，与单向链表一样
function findLast() {
  var currNode = this.head;
  while (currNode.next) {
    currNode = currNode.next;
  }
  return currNode;
}

// 删除指定元素
function remove(item) {
  if (item === 'head') { // 不能删除头节点
    return;
  }

  var removeItem = this.find(item)
  if (!removeItem) {
    return
  }

  removeItem.previous.next = removeItem.next

  if (removeItem.next) {
    removeItem.next.previous = removeItem.previous;
  }

  removeItem.previous = null;
  removeItem.next = null;
  this.size--;
}

// 清空链表
function clear() {
  this.head.next = null;
  this.size = 0;
}

// 向链表尾部添加元素
function append(item) {
  var lastNode = this.findLast()
  var newNode = new Node(item)
  lastNode.next = newNode;
  newNode.previous = lastNode;
  this.size++;
}

// 从前向后展示链表
function display() {
  console.log('当前元素数量为: ', this.size);
  if (this.size === 0) {
    return;
  }
  var currNode = this.head;
  while (currNode && currNode.next != null) {
    console.log(currNode.next.element);
    currNode = currNode.next
  }
}

// 从后向前展示链表
function dispReverse() {
  console.log('当前元素数量为: ', this.size);
  if (this.size === 0) {
    return;
  }

  console.log('从后往前输出：');

  var currNode = this.findLast();
  while (currNode && currNode.previous != null && currNode.element != 'head') {
    console.log(currNode.element);
    currNode = currNode.previous
  }
}

测试代码：

var l = new TwoWayLinkedList();

l.append('Anna')
l.append('Clayton')
l.display() // Anna Clayton

l.dispReverse() // Clayton Anna 

l.insertBefore('Brown', 'Clayton')
l.display() // Anna Brown Clayton

l.dispReverse()  // Clayton Brown Anna 

l.append('David')
l.remove('Clayton')
l.display() // Anna Brown David

l.dispReverse() // David Brown Anna 

l.insertBefore('test', 'Clayton') // 在一个不存在的元素之前插入
l.display() // Anna Brown David

l.dispReverse() // David Brown Anna 

l.insertAfter('Cynthia', 'Brown')
l.display() // Anna Brown Cynthia David

l.dispReverse() // David Cynthia Brown Anna

循环链表

循环链表和单向链表相似，节点类型都是一样的，唯一的区别是，在初始化时头节点的 next 属性指向头节点本身，这种行为会传导至链表中的每个节点，使得每个被 append 的节点的 next 属性都指向链表的头节点，以形成循环列表；

function Node(element) {
  this.element = element;
  this.next = null;
}

function CircularLinkedList() {
  this.head = new Node('head')
  this.head.next = this.head;
  this.size = 0;
  this.find = find;
  this.insertBefore = insertBefore;
  this.insertAfter = insertAfter;
  this.display = display;
  this.remove = remove;
  this.findPrevious = findPrevious;
  this.findLast = findLast;
  this.append = append;
}

function find(item) {
  if (this.size === 0) { // 确保有元素存在，才进行查找
    return;
  }
  var currNode =  this.head;
  while(currNode && currNode.element != item && currNode.next.element !== 'head') {
    currNode = currNode.next;
  }
  return currNode;
}

function findLast() {
  var currNode = this.head;
  while (currNode && currNode.next && currNode.next.element !== 'head') {
    currNode = currNode.next;
  }
  return currNode;
}

function append(item) {
  var lastNode = this.findLast()
  var newNode = new Node(item)
  lastNode.next = newNode;
  newNode.next = this.head;
  this.size++;
}

function display() {
  console.log('当前元素数量为: ', this.size);
  if (this.size === 0) {
    return;
  }
  var currNode = this.head;
  while (currNode && currNode.next != null && currNode.next.element !== 'head') {
    console.log(currNode.next.element);
    currNode = currNode.next
  }
}

function findPrevious(item) {
  if (this.size === 0) {
    return null
  }

  var currNode = this.head;
  while (currNode.next != null && currNode.next.element != item && currNode.next.element !== 'head') {
    currNode = currNode.next
  }

  if (currNode.next.element === 'head') { // 是最后一个节点
    return null
  }

  return currNode;
}

function insertBefore(newElement, existingItem) {
  var anchorItem = this.findPrevious(existingItem)
  if (!anchorItem) {
    return;
  }
  var newNode = new Node(newElement)
  var existingNode = this.find(existingItem)
  newNode.next = existingNode;
  anchorItem.next = newNode;
  this.size++;
}

function insertAfter(newElement, existingItem) {
  var anchorItem = this.find(existingItem)
  if (!anchorItem) {
    return;
  }
  var newNode = new Node(newElement)
  newNode.next = anchorItem.next;
  anchorItem.next = newNode;
  this.size++;
}

function remove(item) {
  var removeItem = this.find(item)
  var prevItem = this.findPrevious(item)
  prevItem.next = removeItem.next;
  removeItem.next = null;
  this.size--;
}

测试代码：

var l = new CircularLinkedList()

l.append('Anna')
l.append('Brown')
l.append('Cynthia')
l.display();  // Anna Brown Cynthia

l.insertBefore('banana', 'Cynthia')
l.display(); // Anna Brown banana Cynthia

l.remove('banana')
l.display(); // Anna Brown Cynthia

l.insertAfter('David', 'Cynthia') 
l.display() // Anna Brown Cynthia David


l.insertAfter('Apple', 'Anna')
l.display() // Anna Apple Brown Cynthia David

l.remove('Apple')
l.display(); // Anna Brown Cynthia David

场景：在公元1世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的40个同胞被罗马士兵包围，犹太士兵决定宁可自杀也不坐俘虏，于是商量出一个自杀方案，它们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将 n 个人围成一圈，并且第 m 个人会被杀掉，计算一圈人中哪两个人最后会存活，使用循环列表解决该问题。

使用链表解决：

for (var i = 0; i < 41; i++) {
  l.append(i+1)
}

var currNode = l.head;
var j = 0;
while (currNode && currNode.next != null && l.size > 2) {
  currNode = currNode.next.element === 'head' ? currNode.next.next : currNode.next;
  j++;
  if (j % 3 === 0) {
    var prev = l.findPrevious(currNode.element)
    console.log(currNode.element);
    l.remove(currNode.element)
    currNode = prev;
    j = 0;
  }
}

l.display() // 16 31

使用数组解决：

var arr = [];
for (var i = 0; i < 41; i++) {
  arr.push(i+1)
}

var j = 0;
var k = 0;
while (arr.length > 2) {
  j++;
  k++;
  k = k > arr.length ? 1 : k;
  if (j % 3 == 0) {
    arr.splice(k-1, 1)
    k--;
    j = 0
  }
}
console.log(arr);  // [16, 31]