链表的概念和用法

链表概念

链表是一种动态的数据结构。跟数组比较，链表的优势是分配内存空间的灵活性，数组的内存却是一块连续的内存。

1. 插入数据来比较

数组插入数据需要插入位置后面的所有元素往后移，消耗大，

而链表的话是将上一个节点的next指向新节点，然后新节点的next指向上一个节点原本指向的节点。

2. 查找数据比较

数组可以直接索引定位

链表需要遍历查找

链表中的节点分为两个部分，一个element代表当前节点数据，一个next代表指向的下一节点。

链表示例

一个可以使用的链表，大概的方法结构如下

function newNode(){ }     //新建节点方法
function findNode(){ }    //查找节点方法
function insertNode(){ }  //插入节点方法
function removeNode(){ }  //删除节点方法
function logNode(){ }     //显示节点方法

那么写一个示例

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

function LinkedList(){
    this.head = new NewNode('head');

    this.findNode = findNode;
    this.insertNode = insertNode;
    this.removeNode = removeNode;
    this.logNode = logNode;
}

/** 查找节点 */
function findNode (item) {
    var curNode = this.head;
    while (curNode.element != item){  //循环链表查找，找不到返回null
        curNode = curNode.next;
    }
    return curNode;
};

/**
 * 插入节点
 * @param newElement 新节点数据
 * @param posItem 插入该节点后面位置
 */
function insertNode (newElement,posItem) {
    var newNode = new NewNode(newElement);
    var posNode = this.findNode(posItem);
    newNode.next = posNode.next;
    posNode.next = newNode;
};

/**
 * 移除节点
 * 找到需要删除节点前一个节点，将next置为被删除节点的next
 */
function removeNode(removeItem){
    var curNode = this.head;
    while(!(curNode.next == null) && curNode.next.element != removeItem){
        curNode = curNode.next;
    }

    if(!(curNode.next == null)){
        curNode.next = curNode.next.next;
    }
}

/** 输出链表全部节点 */
function logNode(){
    var curNode = this.head;
    var listArr = [];
    while(curNode.next != null){
        listArr.push(curNode.next.element);
        curNode = curNode.next;
    }

    return listArr;
}

var list = new LinkedList();
list.insertNode('cont1' , 'head');
list.insertNode('cont2' , 'cont1');
list.insertNode('cont3' , 'cont2');

console.log(list.logNode());  //['cont1' , 'cont2' , 'cont3' ]

list.removeNode('cont2');

console.log(list.logNode());  //['cont1' , 'cont3' ]

参考链接