链表

一、链表简介

1.1引入链表

一、前面我们已经学习了顺序表，它有优点也有缺点。
缺点：
1.插入元素时，最坏情况如果插入到第一个位置，时间复杂度为O（n），当有许多元素时，效率就会很低。
2.删除数据时，也是同样的，因为要从后往前移动元素，最坏情况，删除0位置，时间复杂度O（n）。
3.扩容时，我们是成倍扩容，那么当我们只增加一个元素时，扩容之后只用掉一个空间，其余空间就会造成浪费。
优点：查找元素时，给定下标进行查找，那么无论查找哪个元素，时间复杂度都是O（1）。
总结：顺序表比较适合进行给定下标查找元素。
二、如何解决？
我们希望的是，插入元素，在扩容时，增加一个元素，那就扩容一个空间，而不是成倍扩容。删除元素时，找到要删除的元素，直接删除，而不是采用移动元素覆盖的方式。
为了解决上面的问题，我们引入了链表这种数据结构。

1.2链表的结构

链表可以类比火车，火车是由一节一节的车厢用铁钩连在一起的，链表也是这样，只不过链表中将车厢叫为节点，节点中分为两块，一块为数据域（data、value域），用于存放数据，一块为next域，用于存放下一个节点的地址，节点与节点之间就是由next域连接而成的。

注：链表在物理上不连续 逻辑上连续。意思就是链表的一个个节点，在实际的内存存储中并不像顺序表那样是连在一起的，因此需要用next域将他们连在一起，但是在学习的过程中，为了方便理解，会将它画的连在一起。

1.3链表的种类

链表可以分为以下几种，但是我们主要掌握的是单向不带头非循环和双向不带头非循环。

带头的和不带头的区别是：不带头的就是一个head变量指向第一个节点，称为头结点，而这个头结点是会改变的，比如在第一个节点前插入节点或是删除第一个节点，head就会指向新的第一个节点。带头的就是一个链表节点，它的data域是空的，next域存第一个节点的地址，它是不会改变的，因此无法在它前面插入节点。

双向的就是相当于一个节点有两个next域，一个指向下一个节点，另一个指向上一个节点。

二、无头单向链表的操作

2.1链表的实现

对于链表，我们将实现以下方法

// 1、无头单向非循环链表实现
public class SingleLinkedList {
//头插法
public void addFirst(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
}
//删除所有值为key的节点
public void removeAllKey(int key){
}
//得到单链表的长度
public int size(){
return -1;
}
public void clear() {
}
public void display() {}
}

2.2如何创建链表

1.顺序表我们可以直接当数组来操作，但是链表我们怎么创建出来？既然它是由一个个节点组成的，那么链表的产生就是不停插入节点。
同样的，我们新建一个接口，放着要实现的抽象方法，一个MySingleList类实现方法，一个Test测试类。
2.在MySingleList类中要先创建出节点，我们采用内部类的方式，因为当一个类由多个若干完整类组成时，我们就可以用内部类，因此我们可以理解为一个MySingleList类由若干个节点内部类组成。
节点类里包括一个data域，和一个next域，next的类型为Linkednode，因为它存放的地址，指向的是一个节点类型。这里不好理解的话，可以类比**Person person = new Person（）；**person指向一个Person类型的对象，因此person的类型也是Person类型，还不理解的话可以类比c语言的指针，存放什么类型数据的地址，那么指针也是对应类型。

public class MySingleList implements IList{
    //一个链表由多个节点构成
    class Linkednode{
        public int data;
        public Linkednode next;
        public Linkednode(int data) {
            this.data = data;
        }
    }
}

注：构造方法只给data赋值，是因为我们还不知道next该指向哪里，还没有找到下一个节点，因此先默认为空。
3.在插入节点时，我们先采用穷举法，创建出来一个个节点，然后将后一个节点的引用赋值给前一个节点的next域，这样我们就将节点连接起来了。此时，只要我们找到第一个节点，那么整个链表都会被找到。

public void createList() {
        //next默认null
        Linkednode node1 = new Linkednode(12);
        Linkednode node2 = new Linkednode(15);
        Linkednode node3 = new Linkednode(8);
        Linkednode node4 = new Linkednode(6);
        Linkednode node5 = new Linkednode(19);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
}

**问题：这些node的引用都是局部变量，那么当这个方法走完之后，这些变量都会被回收，意味着这些节点没有被引用（即没有指向它的引用），那么所有节点就会被回收。

解决：我们可以定义一个头节点引用，将第一个节点的地址赋值给头节点引用，这样即使node的引用都被回收，但是第一个节点依然被head指着，节点就不会被回收。
注：head不属于每个节点的属性，是属于整个链表的属性，因此，定义到内部类外。

class Linkednode{
        public int data;
        public Linkednode next;
        public Linkednode(int data) {
            this.data = data;
        }
    }
    public Linkednode head;
    public void createList() {
        //next默认null
        Linkednode node1 = new Linkednode(12);
        Linkednode node2 = new Linkednode(15);
        Linkednode node3 = new Linkednode(8);
        Linkednode node4 = new Linkednode(6);
        Linkednode node5 = new Linkednode(19);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

2.3 display（）遍历链表打印

遍历链表我们要解决两个问题：
1.一个节点如何走到下一个节点
2.如何判断所有节点遍历完
解决：我们可以用head来遍历，因为每个节点的next域都存着下一个节点的地址，那么只用将next域的值赋给head，head就走到下一个节点了。判断走完也很简单，当head指向空时就遍历完了。head=head.next head

问题：head指向空了，就找不到第一个节点了 ，找不到第一个节点，那么后面的节点也都找不到了，因此我们不能让head移动，重新定义一个cur来移动。

public void display() {
        Linkednode cur = head;
        while (cur!=null){
            System.out.println(cur.data);
            cur = cur.next;
        }

2.4 int size()节点个数

与遍历链表相同，只是需要再定义一个计数变量统计。

public int size() {
        int count = 0;
        Linkednode cur = head;
        while (cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }

2.4 boolean contains(int key)查询是否包含某个元素

遍历链表，看data域是否等于key。

public boolean contains(int key) {
        Linkednode cur = this.head;
        while (cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

2.5 void addFirst(int data)头插法

头插法：考虑两种情况一个是链表为空一种是不为空
**首先，要先有新节点，所以在操作之前要先实例化一个新节点。

Linkednode newnode = new Linkednode(data);

1.链表为空**
即head没有指向任何节点，那么直接将新节点的引用赋值给head即可。
2.链表不为空
分为两步：一是将新节点与原先第一个节点建立联系，即将原先第一个节点的地址赋值给新节点的next域；而是将head指向新节点。

public void addFirst(int data) {
        Linkednode newnode = new Linkednode(data);
        if(head==null){
            head = newnode;
        }else {
            newnode.next = head;
            head = newnode;
        }

    }

其实不用分情况直接用else里的那两行代码也是可以的。
此时我们就不用之前的穷举法了，直接调用这个头插法创建链表即可。

public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addFirst(6);
        mySingleList.addFirst(19);
        mySingleList.addFirst(8);
        mySingleList.addFirst(15);
        mySingleList.addFirst(1003);
        mySingleList.display();
        System.out.println(mySingleList.size());


    }

因为是头插，所以顺序是倒的。

2.6 public void addLast(int data)尾插法

一样的先实例化新节点如果为空直接赋值。
不为空，我们要考虑的问题是：如何找到最后一个节点？最后一个节点的特点是next域为空，因此当cur的next域为空时就停止，然后将最后一个节点的next域赋值为新节点的引用即可。

public void addLast(int data) {
        Linkednode newnode = new Linkednode(data);
        Linkednode cur = head;
        if(cur == null){
            head=newnode;
        }else {
            //找到最后一个节点
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=newnode;
        }
    }

注：判断条件要和前面的遍历区分开，前面的（while (cur!=null)）遍历完之后cur指向空，而这个判断条件（cur.next!=null）是让cur指向最后一个节点。

2.7 void addIndex(int index, int data)在任意位置增加节点

1.先判断index是否合法，写一个自定义异常。
2.如果index等于0则直接调用头插法
3.如果index等于size直接调用尾插法
4.如果是在中间位置，我们先看一下结果

a.如何找到要操作的位置
因为链表没有下标，所以人为加上，假设要在下标为3的位置插入元素，我们将cur走到3位置，结果发现没有用，因为我们操作的是节点的前驱，再加上链表是单向的，不能往回走，所以cur要走到index的前一个位置如何走？让cur走index-1步即可。
b.插入节点

public void addIndex(int index, int data) {
        if(index<0 || index>this.size()){
            try {
                checkindex(index);
            }catch (PosIllegality e) {
                e.printStackTrace();
                return;
            }
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        Linkednode newnode = new Linkednode(data);
        Linkednode cur = seacherpre(index);
        newnode.next = cur.next;
        cur.next = newnode;
    }
    //找前驱节点
    public Linkednode seacherpre(int index){
        Linkednode cur = head;
        int count = 0;
        while (count != index-1 ) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

2.8 void remove(int key)删除指定值

分三步走：
1.判断是否存在key值
2.找到要删除的值的前驱
3.删除
a.链表为空 直接返回
b.如果头结点为目标值 则直接将head指向下一个节点

这时会发现有一个节点被两个引用所指着，但是del是局部变量，当方法走完，它就被自动回收了，所以不用担心。

public void remove(int key) {
        //链表为空
        if(head == null){
            return;
        }
        //头结点为目标值
        if(head.data == key){
            head = head.next;
            return;
        }
        //1.找前驱
        Linkednode cur = findpre(key);
        //2.判断是否存在
        if(cur == null){
            System.out.println("这个值不存在 无法删除");
            return;
        }
            //3.删除
            Linkednode del = cur.next;
            cur.next = del.next;
    }
    public Linkednode findpre(int key){
        Linkednode cur = this.head;
        while (cur.next != null) {
            if(cur.next.data == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

2.9 void removeAllKey(int key)删除所有的key值

前面我们只是删除掉了一个指定值，这次的方法要删除所有的key值。先不看头结点，首先定义一个cur用来遍历链表，当cur找到了key值时，光用它是无法删除的，因为要找到它的前驱节点，因此还要定义一个pre用来指向要删除的节点的前驱节点。

假设删除15，开始遍历：
1.pre = head
2.cur = head.next
3.如果cur.data = key 改变pre的指向 然后移动cur

4.如果cur.data != key

就这样，直到cur遍历完整个链表。最后，再判断head是否为key值，如果一开始就先判断head的话，就得再写一个循环。

public void removeAllKey(int key) {
        if(head == null){
            return;
        }
        Linkednode cur = head.next;
        Linkednode pre = head;
        while (cur!=null){
            if(cur.data==key){
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        if(head.data==key){
            head = head.next;
        }
    }

2.10 void clear( )清空链表

第一种粗暴的方式就是将head置空，此时头结点没有被引用，那么当方法结束后，头结点自动被回收，之后的节点都会被回收。
第二种就是遍历链表，将每一个节点的数据域和节点域置空。用cur来遍历链表，如果只用一个cur，那么当cur置空next域时，就无法移动到下一个节点，因此要再定义一个curNext来记录它的下一个节点。

三、无头双向链表的实现

双向链表与单向链表比起来，最大的差别就是双向链表多了一个地址域，用来记录前面节点的地址，这样链表就可以双向走，而不是只能走一个方向。

3.2 创建链表

创建双向链表与单向的差不多，只不过双向的多了一个prev域和一个last指针。

    static class ListNode{
        public int data;
        public ListNode next;
        //前驱指针域
        public ListNode prev;

        public ListNode(int data) {
            this.data = data;
        }
    }
    public ListNode head;
    //尾结点
    public ListNode last;

3.3 打印、是否包含某个节点、计算链表长度

这三个方法不用prev前驱域，与单向链表是一样的写法。

public void display() {
        ListNode cur = head;
        while (cur!= null){
            System.out.println(cur.data+" ");
            cur = cur.next;
        }
    }
public int size() {
        int size = 0;
        ListNode cur = head;
        while (cur!= null) {
            size++;
            cur = cur.next;
        }
        return size;
    }
public boolean contains(int key) {
        ListNode cur = head;
        while (cur!= null){
            if(cur.data==key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

3.4 头插法和尾插法

双向链表的头插法和尾插法比单向多了prev这一步，还要注意给prev赋值，另外，因为双向链表有last节点，因此在尾插的时候，可以直接找到last节点然后插入，不用像单向链表还要遍历找到最后一个节点。如果是第一次插入，那么head和last节点都先指向新节点

3.5 在某个位置插入

先判断index是否合法，抛异常，和单向一样。
如果为0，头插法，如果为size，尾插法。
在合法的某个位置，先找到那个节点，然后插入，一定要注意顺序

public void addIndex(int index, int data) {
        if(index<0 || index>this.size()){
            try {
                checkindex(index);
            }catch (PosIllegality e) {
                e.printStackTrace();
                return;
            }
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode newnode = new ListNode(data);
        ListNode  cur = seacher(index);
        
    }
    //异常
    private void checkindex(int pos) throws PosIllegality {
        if (pos < 0 || pos > size()) {
            System.out.println("不符合法！");
            throw new PosIllegality("插入元素下标异常: " + pos);
        }
    }
    //找要插入位置的那个节点
    private ListNode seacher(int index){
        ListNode cur = head;
        while (index!=1){
            cur = cur.next;
            index--;
        }
        return cur;
    }

3.6 删除某个节点

先找到要删除的节点，看这个节点是否存在，如果是空链表，返回空，如果头结点为目标值

如果是最后一个节点

如果是中间节点

还要注意只有一个节点并且这个节点刚好是目标值的情况

public void remove(int key) {
        //链表为空
        if(head == null){
            return;
        }
        //头结点为目标值
        if(head.data == key){
            head = head.next;
            //判断是否只有一个节点
            if(head!=null) {
                head.prev = null;
                return;

            }
            last = null;
        }
        //尾结点为目标值
        if(last.data == key){
            last = last.prev;
            //判断是否只有一个节点
            if(last!=null){
                last.next = null;
                return;
            }
            head = null;
        }
        //1.中间节点为目标值 找要删除的节点
        ListNode cur = find(key);
        //2.判断是否存在
        if(cur == null){
            System.out.println("这个值不存在 无法删除");
            return;
        }
        //3.删除 中间节点
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
    }
    private ListNode find(int key){
        ListNode cur = head;
        while (cur!=null){
            if(cur.data == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

经过优化，代码如下

3.7 删除所有值为key的节点

public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.data == key) {
            //如果是头结点
                if(cur == head) {
                    head = head.next;//head == null
                    //如果只有一个头结点 已经删除完了
                    if(head == null) {
                    //那么last也要置空
                        last = null;
                        //如果不只有头结点
                    }else {
                        head.prev = null;
                    }
                }else {
                //cur不是头结点
                    cur.prev.next = cur.next;
                    //如果是最后一个节点
                    if(cur.next == null) {
                    //last往前移动
                        last = last.prev;
                    }else {
                    //如果不是最后一个节点
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }

    }

3.8 清空链表

public void clear() {
        /* ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            //cur.val = null;
            cur.prev = null;
            cur.next = null;
            cur = tmp;
        }*/
        head = null;
        last = null;
    }

调试方法
打上断点debug，然后cmd，以管理员身份运行，输入jps，会显示正在运行的进程，jmap -histo：live 进程号>输入到某个文件中，ctrl+F查找元素看是否内存泄露。

//如果不是最后一个节点
                    cur.next.prev = cur.prev;
                }
            }
        }
        cur = cur.next;
    }

}

#### 3.8 清空链表

public void clear() {
/* ListNode cur = head;
while (cur != null) {
ListNode tmp = cur.next;
//cur.val = null;
cur.prev = null;
cur.next = null;
cur = tmp;
}*/
head = null;
last = null;
}

**调试方法**
打上断点debug，然后cmd，以管理员身份运行，输入jps，会显示正在运行的进程，jmap -histo：live 进程号>输入到某个文件中，ctrl+F查找元素看是否内存泄露。