基础数据结构--手动实现链表及其相关方法

单向链表

链表的定义：链表是由一组节点组合而成的集合，每个节点都使用一个对象的引用指向他的后继。指向另一个节点的引用叫做链。链表靠他们相互之间的关系进行引用。所以对于链表的操作也很简单，既，查找，删除，插入等。只是改变元素的指向关系即可。
实现链表：

function Node (item) {
    //  element保存节点上的数据
    this.element = item
    //  next表示指向下一个节点的链
    this.next = null
}
function Llist () {
    //  链表的头
    this.header = new Node('head')
    //  查找链表元素
    this.find = find
    //  向链表中插入元素
    this.insert = insert
    //  删除链表的某一个元素
    this.remove = remove
}
function find (item) {
    //  拿到列表的头节点
    let currNode = this.header
    while(currNode !== item) {
        //  如果当前节点不是要找的节点
        //  就指向下一个节点
        currNode = currNode.next
    }
    return currNode
}
function insert (newItem, oldItem) {
    //  先找到要在插入元素的前一个元素
    let currNode = this.find(oldItem)
    const newNode = Node(newItem)
    //  前一个元素指向新节点
    currNode.next = newNode
    //  新元素指向之前元素的下一个
    newNode.next = currNode.next
}
function remove (item) {
    //  首先要找到前一个元素
    var currNode = this.header
    while (!(currNode ===  null) &&
        currNode.next.element !== item) {
            currNode = currNode.next
        }
    if (!(currNode.next === null)) {
        currNode.next = currNode.next.next
    }
}

双向链表

双向了链表较单项链表而言，双向链表比单向链表要多一个属性，就是前驱。这样在删除元素的时候，就不需要再查找前一个元素了。也就是说，每个元素总有一个属性，指向了他的前一个元素。

function Node (item) {
    this.element = item
    this.next = null
    this.previous = null
}
function Llist () {
    this.header = new Node('head')
    this.find = find
    this.remove = remove
    this.insert = insert
    //  查找最后一个元素
    this.findLast = findList
}
function find (item) {
    let currNode = this.header
    while (!(currNode.element === item)) {
        currNode = currNode.next
    }
    return currNode
}
function insert (newElement, item) {
    let curr = this.find(item)
    let newNode = new Node(newElement)
    curr.next = newNode
    newNode.next = curr.next
    newNode.previous = curr
}
function remove (item) {
    let curr = this.find(item)
    if (!(curr.next === item)) {
        curr.previous.next = curr.next
        curr.next.previous = curr.previous
        curr.next = null
        curr.previous = null
    }
}
function findLast (item) {
    let curr = this.header
    while (!(curr.next === item)) {
        curr = curr.next
    }
    return curr
}

循环链表

循环链表和单向链表很相似，唯一的区别就是循环链表的头节点的next属性指向自己。

function Llist (item) {
    this.header = new Node(item)
    this.header.next = this.header
    .
    .
    .
}

That’s all!