Skip to content

Latest commit

 

History

History
318 lines (264 loc) · 8.37 KB

2018-2-24-LList.md

File metadata and controls

318 lines (264 loc) · 8.37 KB
Raw

再剖析数据结构与算法 javascript 描述--链表（LList）

链表的定义

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

链表的实现都在链表最前面有一个特殊节 点，叫做头节点。遍历链表，就是跟着 链接，从链表的首元素一直走到尾元素(但这不包含链表的头节点，头节点常常用来作为 链表的接入点)。链表的尾元素指向一个 null 节点。

单向链表

链表中的元素都会又一个前驱，通过前驱的指向来操作链表元素的添加和删除。一个完整的单项链表操作如下图：

定义单向链表类

根据以上图解，一个链表基本有两个类组成，节点类和链表的操作类，可以大致总结该链表所包含的属性和方法，基本如下：

节点类（Node 类）

属性/方法 描述
element(属性) 节点类的元素
next(属性) 节点类的前驱指向

操作类（Llist 类）

属性/方法 描述
head(属性) 继承节点类并且创建头节点
find(方法) 查找节点方法
insert(方法) 插入节点方法
remove(方法) 删除节点的方法
findPrevious(方法) 找到待删除节点前面的节点方法
display(方法) 显示链表的方法

在添加节点的时候，只要判断当前节点的next属性指向你需要添加的节点，并且新添加的节点的next属性指向上一个节点原先指向的属性。核心代码如下：

insert(newElement, item) {
    let newNode = new Node(newElement)
    let current = this.find(item)
    newNode.next = current.next
    current.next = newNode
}

删除节点操作与添加节点类似，原理基本一样，核心代码如下：

// 找到待删除节点前面的节点
  findPrevious(item) {
    let currNode = this.head;
    while (!(currNode.next === null) &&
      (currNode.next.element !== item)) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 删除节点的方法
  remove(item) {
    let prevNode = this.findPrevious(item);
    if (!(prevNode.next === null)) {
      prevNode.next = prevNode.next.next;
    }
  }

此单向链表完整代码如下：

// node类，保存节点的数据以及下一个节点的连接
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

// LList类，插入，删除等方法
class LList {
  constructor() {
    this.head = new Node('head')
  }

  // 查找节点方法
  find(item) {
    let currNode = this.head
    while (currNode.element !== item) {
      currNode = currNode.next
    }
    return currNode
  }

  // 插入节点方法
  insert(newElement, item) {
    let newNode = new Node(newElement)
    let current = this.find(item)
    newNode.next = current.next
    current.next = newNode
  }

  // 显示链表的方法
  display() {
    let currNode = this.head
    while (!(currNode.next === null)) {
      console.log(currNode.next.element)
      currNode = currNode.next
    }
  }

  // 找到待删除节点前面的节点
  findPrevious(item) {
    let currNode = this.head
    while (!(currNode.next === null) && currNode.next.element !== item) {
      currNode = currNode.next
    }
    return currNode
  }

  // 删除节点的方法
  remove(item) {
    let prevNode = this.findPrevious(item)
    if (!(prevNode.next === null)) {
      prevNode.next = prevNode.next.next
    }
  }
}

双向链表

从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过 给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链 表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表 中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。基本操作如下图：

定义双向链表类

通过上图可以了解到，双向链表中，对于Node类增加了一个previous属性作为后继的定义，对于添加和删除节点还需要只想相应节点的后继指向，修改片段代码如下：

class Node {
  constructor(element) {
    this.element = element
    this.next = null
    this.previous = null
  }
}

// 将一下代码放入之前的Llist类中
// 插入节点方法
insert(newElement, item) {
    let newNode = new Node(newElement)
    let current = this.find(item)
    newNode.next = current.next
    newNode.previous = current
    current.next = newNode
}

// 删除节点的方法
  remove(item) {
    let currNode = this.find(item)
    if (!(currNode.next === null)) {
      currNode.next = currNode.next.next
      currNode.next.previous = currNode.previous
      currNode.next = null
      currNode.previous = null
    }
  }

扩展双向链表类

找出了链表中的最后一个节点findLast方法 反序显示双向链表中的元素dispReverse方法 显示当前节点方法show方法 向前移动 n 个节点advance方法 向后移动 n 个节点back方法

扩展后的链表完整代码如下：

// node类，保存节点的数据以及下一个节点的连接
class Node {
  constructor(element) {
    this.element = element
    this.next = null
    this.previous = null
  }
}

// LList类，插入，删除等方法
class LList {
  constructor() {
    this.head = new Node('head')
    this.currNode = null
  }

  // 查找节点方法
  find(item) {
    let currNode = this.head
    while (currNode.element !== item) {
      currNode = currNode.next
    }
    return currNode
  }

  // 插入节点方法
  insert(newElement, item) {
    let newNode = new Node(newElement)
    let current = this.find(item)
    newNode.next = current.next
    newNode.previous = current
    current.next = newNode
  }

  // 显示链表的方法
  display() {
    let currNode = this.head
    while (!(currNode.next === null)) {
      console.log(currNode.next.element)
      currNode = currNode.next
    }
  }

  // 找出了链表中的最后一个节点
  findLast() {
    let currNode = this.head
    while (!(currNode.next == null)) {
      currNode = currNode.next
    }
    return currNode
  }

  // 反序显示双向链表中的元素
  dispReverse() {
    let currNode = this.head
    currNode = this.findLast()
    while (!(currNode.previous == null)) {
      print(currNode.element)
      currNode = currNode.previous
    }
  }

  // 删除节点的方法
  remove(item) {
    let currNode = this.find(item)
    if (!(currNode.next === null)) {
      currNode.next = currNode.next.next
      currNode.next.previous = currNode.previous
      currNode.next = null
      currNode.previous = null
    }
  }

  // 显示当前节点方法
  show() {
    return this.currNode
  }

  // 向前移动n个节点
  advance(n) {
    let currNode = this.head
    let idx = 0
    while (!(currNode.next === null) && idx < n) {
      ++idx
      currNode = currNode.next
    }
    this.currNode = currNode
    return currNode
  }

  // 向后移动n个节点
  back(n) {
    let currNode = this.findLast()
    let idx = 0
    while (!(currNode.next === null) && idx < n) {
      ++idx
      currNode = currNode.next
    }
    this.currNode = currNode
    return currNode
  }
}

循环链表

基本与单向链表和双向链表类似，唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，片段代码如下：

head.next = head

基本图解如下：

因此只需根据单项链表做如下修改，基本代码如下：

class LList {
  constructor() {
    this.head = new Node('head')
    this.head.next = this.head
  }

  // 显示链表的方法
  display() {
    let currNode = this.head
    while (!(currNode.next == null) && !(currNode.next.element == 'head')) {
      console.log(currNode.next.element)
      currNode = currNode.next
    }
  }
}