数据结构：LinkedList与链表—无头单向链表（一）

一、ArrayList的缺陷

在前面我们已经学习了List和ArrayList，知道了List其实是一个线性表在这上面可以执行增删改查以及变量等操作，而ArrayList实现了List接口，这使ArrayList同样具备这些功能，而ArrayList的底层是使用数组实现的，因此他的优点和缺点也和数组类似

优点：

1、根据下标遍历元素效率较高

2、根据下标访问元素效率较高

3、在数组的基础上封装了对元素操作的方法

4、可以扩容

我们看到这些优点其实非常的好，但是他的缺点也十分的明显 

缺点：

1、插入和删除的效率比较低

当我们在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，这导致了他的时间复杂度变成了O(N),这也导致了他的效率比较低

2、内存浪费

ArrayList在扩容的时候，通常会预留一定的容量，以减少频繁的扩容开销，但是这就导致了在存储少量数据的时候，实际占用的内存远大于所需的内存，这就导致了大量内存的浪费。

3、动态扩展效率低

由于ArrayList的底层是数组实现的，当数组容量不足时，就会创建一个更大的数组，并将旧数组的元素复制到新数组中这种扩容操作，在面对大量数据时可能会导致性能问题

而为了避免一些缺陷，像插入和删除，Java集合中有又引入了LinkedList，即链表结构，同样是实现了List接口。

二、链

1、链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

这么说大家可能并不明白我们来看下面这张图

链表在物理上的存储结构可能是像上面的一样，但是他们之间又像又一条链子一些链接在一起，这就形成了下面的样子

因此链式结构在逻辑上是连续的，在物理上不一定连续，而这样的形态也就导致了我们在进行元素的插入和删除的时候，不需要将后序元素整体往前或者往后搬移，只需要将要插入和删除的元素链接或断开即可。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

（1）单向或者双向

（2）带头或者不带头

注意：这里的头是一个固定的结点，不发生改变

单向

双向 

（3）循环或者非循环

单向

而这三样形式可以组合成8中类型分别是：

单向 带头 循环

单向 带头 非循环

单向 不带头 循环

单向 不带头 非循环

双向 带头 循环

双向 带头 非循环

双向 不带头 循环

双向 不带头 非循环

  

虽然有这么多的链表的结构，但是我们重点掌握两种: 

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 

而今天我们主要要讲的是无头单向非循环链表。

2、无头单向非循环链表的实现 

模拟实现一个Ilist接口

创建一个SingleLinkedList类实现IList接口，在类中创建一个结点，在结点中设置一个变量用来接收数据，和一个next进行结点之间的链接 。之后创建一个头结点（但是我们要实现的不是无头的链表吗？为什么要有头结点呢？其实这个结点并不是所谓固定的头节点，他只是用来存储第一个结点的引用而已）和有效长度变量。

（1）display()方法

打印链表

（5）addFirst(int data)方法

 头插法

（3）addLast(int data)方法

尾插法

（4）addIndex(int index,int data)方法

任意位置插入 , 第一个数据节点为 0 号下标

（5）contains(int key)方法

查找是否包含关键字 key 是否在单链表当中

（6）remove(int key)方法

删除第一次出现关键字为 key 的节点

（7）removeAllKey(int key)方法

删除所有值为 key 的节点

注意：这里头结点的判断必须放到最后，因为如果当前三个数都是要删除的数是如果现判断了头结点，进行了删除这样就会导致第二个数成为新的头结点而后面的操作是没有删除头节点的功能的这就导致第二个数没有被删除 

（8）size()方法

得到单链表的长度

（9）clear()方法

清空链表

我们可以将所有的元素置为空

（10）完整代码

IList接口

public interface IList {
    //头插法
    void addFirst(int data);

    //尾插法
    void addLast(int data);

    //任意位置插⼊第⼀个数据节点为0号下标
    void addIndex(int index,int data);

    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);

    //删除第⼀次出现关键字为key的节点
    void remove(int key);

    //删除所有值为key的节点
    void removeAllKey(int key);

    //得到单链表的⻓度
    int size();

    //清空链表
    void clear();

    //打印链表
    void display();
}

 SingleLinkedList类

public class SingleLinkedList implements IList {

    static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public int listsize;

    @Override
    public void display() {
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
        this.listsize++;
    }
    @Override
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.listsize++;
            return ;
        }
        ListNode cur = this.head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
        listsize++;
    }
    @Override
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        try{
            check(index);
            if(index == 0){
              addFirst(data);
              return;
            }
            if(index == this.listsize){
              addLast(data);
              return;
            }
            ListNode cur = findindex(index);
            node.next = cur.next;
            cur.next = node;
            this.listsize++;

        }catch (Illegality e){
            e.printStackTrace();
        }

    }
    public void check(int index) throws Illegality{
        if( index < 0 || index > this.listsize){
            throw new Illegality("index不合法");
        }
    }
    private ListNode findindex(int index){
        ListNode cur = this.head;
        int count = 0;
        while(count != index-1 ){
            cur = cur.next;
            count++;
        }
        return cur;
    }
    @Override
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
        }
        return false;
    }
    @Override
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        try {
            empty();
            if(this.head.val == key ){
                this.head = this.head.next;
                return;
            }
            ListNode cur = findlist(key);
            if (cur == null) {
                System.out.println("没有");
                return;
            }
            ListNode del = cur.next;
            cur.next = del.next;
            this.listsize--;
        }catch (EmptyTable e){
            e.printStackTrace();
        }
    }
    public void empty() throws EmptyTable{
        if(this.head == null){
            throw new EmptyTable("链表为空");
        }
    }
    private ListNode findlist(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
        }
        return null;
    }
    @Override
    //删除所有值为key的节点
    public void removeAllKey(int key){
        try {
            empty();
            ListNode cur = this.head.next;
            ListNode prev = this.head;
            while (cur != null) {
                if (cur.val == key) {
                    prev.next = cur.next;
                    this.listsize--;
                } else {
                    prev = cur;
                }
                cur = cur.next;
            }

            if (head.val == key) {
                head = head.next;
                this.listsize--;
            }
        }catch (EmptyTable e){
            e.printStackTrace();
        }
    }
    @Override
    //得到单链表的长度
    public int size(){

        return this.listsize;
    }

    @Override
    public void clear(){
        ListNode cur = this.head;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN;
        }
         this.head = null;
         this.listsize = 0;
    }
}

异常 

public class Illegality extends RuntimeException{
    public Illegality(String message){
        super(message);
    }
}

public class EmptyTable extends RuntimeException{
    public EmptyTable(String message){
        super(message);
    }
}

主函数 

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();

    }
}

好了今天的内容就到这里了，我们下一篇再见！