链表

JS中可以动态的向数组中添加删除元素，所以不需要链表结构。
链表特点：

• 添加、删除元素很快，不需要进行移动。
• 单链表：每个元素都要保存一个指针，指向下一个元素。
• 双链表：每个元素既要保存指向下一个元素的指针，还要保存指向上一个元素的指针。
• 循环链表：最后一个元素中保存指向第一个元素的指针。

1. 链表与数组区别：

1.数组：事先定义固定的长度，不能动态增减，会导致内存浪费。
链表：可以动态分配内存，动态增减，不会造成内存浪费，方便得插入、删除。

2.数组：顺序存储
链表：随机存储

3.数组：从栈中分配空间，方便快速，自由度小。
链表：从堆中分配空间，自由度大，申请管理麻烦。

4.数组：有越界问题。
链表：没有越界问题。

2. 什么时候选择顺序表？什么时候选择链表作为线性表得存储结构？

a.空间上：顺序表静态分配内存，线性表动态分配内存，如果长度变化不大，可以事先确定的用顺序表，长度变化较大，事先无法确定的用链表。

b.时间上：如果在线性表上的操作主要为查找，很少删除插入则用顺序表；反之，则用链表。

3. 如何使用链表头？

Paste_Image.png

头节点的作用：
1.在插入和删除结点时，需要修改前面结点的指针，如果没有头节点，则对开始结点前的插入删除比较麻烦。
2.头指针指向头结点，保证空表与飞空表的处理是一样的。

4. 如何实现单链表的插入、删除？

插入：在ai之前插入一个元素x
1.找到ai-1的存储位置P；
2.生成一个数据域为x的新节点；
3.将P的指针域指向新节点
4.新节点的指针域指向ai
主要的操作耗费在查找P位置，所以时间复杂度为O(n)

删除：删除ai
1.找到ai-1的存储位置P；
2.将P指针域指向ai+1;
3.释放ai结点空间。

function Node(element) {//结点定义
        this.element=element;
        this.next=null;
    }
    function LList() {  //链表方法
        this.head=new Node("head");
        this.find=find;
        this.insert=insert;
        this.remove=remove;
        this.findPrevious=findPrevious;
        this.display=display;
    }
    function find(item) {  //找到元素item
        var currNode=this.head;
        while(currNode.element!=item){
            currNode=currNode.next;
        }
        return currNode;
    }
    function insert(newElement,item) {//向item后面插入newElement
        var newNode=new Node(newElement);
        var current=this.find(item);
        newNode.next=current.next;
        current.next=newNode;
    }
    function findPrevious(item) {//找到item前面的结点
        var currNode=this.head;
        while ((currNode.next!=null)&&(currNode.next.element!=item)){
            currNode=currNode.next;
        }
        return currNode;
    }
    function remove(item) {  //删除元素值为Item的结点
        var prevNode=this.findPrevious(item);
        if(prevNode.next!=null) {
            prevNode.next = prevNode.next.next;
        }
    }
    function display() {  //输出链表
        var currNode=this.head;
        while (currNode.next!=null){
            console.log(currNode);
            currNode=currNode.next;
        }
        console.log(currNode);
    }
    var cities=new LList();
    cities.insert("A","head");
    cities.insert("C","A");
    cities.remove("C");
    cities.display();