手动实现单链表的源码

下面是Java版的链表源码： 

// 无头单向非循环链表实现
public class SingleLinkedList {
    // 链表是有一个一个的节点组成，因此得先创建节点
    // 链表的节点由两部分组成：数值域与地址域
    // 既然有多个部分，那么就可以写在类中
    // 又因为节点是在单链表中（单链表中包含一个又一个的节点）
    // 因此节点就可以成为单链表的内部类

    // 静态内部类可以只通过类名来访问，方便
    public static class listNode {
        public int val; // 存放数值
        // 是一个引用指向下一个节点的地址
        public listNode next; // 指向下一个节点的地址

        public listNode(int val) {
            // 新创建的节点的next应该为null，因为next为字段。因此其默认值为null，无需修改
            this.val = val;
        }
    }

    public listNode head; // 头节点

    // 头插法
    public void addFirst(int data){
        listNode newNode = new listNode(data);
        // 先判断这个链表是否有节点
        if (head == null) {
            //那么新增的这个节点就是头节点
            head = newNode;
        }else {
            // 把新节点的next指向head，并且把head指向新节点
            newNode.next = head;
            head = newNode;
        }
    }

    // 尾插法
    public void addLast(int data){
        listNode newNode = new listNode(data);
        // 先判断这个链表是否为空
        if (head == null) {
            head = newNode;
        }else {
            listNode cur = head;
            // 找到尾节点
            while (cur.next != null) {
                cur = cur.next;
            }
            // 将尾节点的next指向新节点，就完成了尾插
            cur.next = newNode;
        }
    }

    // 任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data) throws AddIndexofException{
        // 先判断插入的位置是否合法
        if (index < 0 || index > size()) {
            throw new AddIndexofException("addIndex() index位置异常");
        }
        // 先判断这个链表是否为空，如果是空，既可以采取尾插，也可以采取头插
        if (head == null) {
            addLast(data);
        }else if (index == 0) {
            addFirst(data);
        }else {
            listNode newNode = new listNode(data);
            // 找到pos-1的位置
            listNode cur = head;
            while (index-1 > 0) {
                cur = cur.next;
                index--;
            }
            // 两个的顺序不能变
            newNode.next = cur.next;
            cur.next = newNode;
            return true;
        }
        return false;
    }

    // 查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        // 先判断链表是否为空
        if (head == null) {
            return false;
        }
        listNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 删除第一次出现关键字为key的节点
    public void remove(int key) throws SingleLinkedisEmptyException, NotFindException{
        // 判断链表是否为空
        if (head == null) {
            throw new SingleLinkedisEmptyException("单链表为空异常");
        } else if (head.next == null) {
            // 如果链表中只有一个元素的话，直接删除就行
            if (head.val == key) {
                head = null;
                return;
            }
            else {
                throw new NotFindException("找不到要删除的数异常");
            }        
        } else if (head.val == key) {
            // 头删
            head = head.next;
            return;
        } else {
            listNode cur = head;
            while (cur.next != null) {
                if (cur.next.val == key) {
                    // 开始删除
                    listNode del = cur.next.next;
                    cur.next = cur.next.next;
                    // 可能这里会有疑惑被删除的节点的next不是还指向了其后一个位置吗？
                    // 这样会不会有问题呢？当一个对象每人引用时，就会被标记回收
                    // 当然手动置为null，也是可以的
                    del = null;
                    return;
                }
                cur = cur.next;
            }
        }
        throw new NotFindException("找不到要删除的数异常");
    }

    // 删除所有值为key的节点
    public void removeAllKey(int key){
        boolean flag = true;
        // 判断链表是否为空
        if (head == null) {
            throw new SingleLinkedisEmptyException("单链表为空异常");
        } else if (head.next == null) {
            // 如果链表中只有一个元素的话，直接删除就行
            if (head.val == key) {
                head = null;
                return;
            }else {
                throw new NotFindException("没有找到要删除的数据！");
            }
        } else if (head.val == key) {
            // 如果头节点的值key，那就循环删除直至头节点的不为key
            while (head.val == key) {
                // 如果删除的只剩下最后一个节点了，就删除返回就行
                if (head.next == null) {
                    head = head.next;
                    return;
                }
            }
            flag = false;
        } else {
            listNode cur = head;
            while (cur.next != null) {
                if (cur.next.val == key) {
                    // 开始删除
                    listNode del = cur.next.next;
                    cur.next = cur.next.next;
                    // 可能这里会有疑惑被删除的节点的next不是还指向了其后一个位置吗？
                    // 这样会不会有问题呢？当一个对象每人引用时，就会被标记回收
                    // 当然手动置为null，也是可以的
                    del = null;
                    flag = false;
                }else {
                    // 可能会出现连续的数字的情况
                    // 因此删除之后，还得判断这个cur之后的元素是否为key
                    cur = cur.next;
                }
            }
        }
        if (flag) {
            throw new NotFindException("找不到要删除的数异常");
        }
    }

    // 得到单链表的长度
    public int size(){
        // 先判断这个链表是否为空
        if (head == null) {
            return 0;
        }
        listNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 打印链表
    public void display(){
        listNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 清空链表
    public void clear(){
        // 暴力解法：把head置为null，那么就没有引用指向这个头节点了
        // 那么这个头节点就会被垃圾回收器给回收掉
        // head = null;

        // 上面那种方式可能会出现不安全的情况，因此采用遍历的形式
        listNode cur = head;
        while (cur != null) {
            // cur.val = null;
            listNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }
}

AddlndexofException异常： 

public class AddIndexofException extends RuntimeException{
    public AddIndexofException() {
        super();
    }

    public AddIndexofException(String msg) {
        super(msg);
    }
}

 NotFindException异常：

public class NotFindException extends RuntimeException{
    public NotFindException() {
        super();
    }

    public NotFindException(String msg) {
        super(msg);
    }
}

 SingleLinkedisEmptyException异常：

public class SingleLinkedisEmptyException extends RuntimeException{
    public SingleLinkedisEmptyException() {
        super();
    }

    public SingleLinkedisEmptyException(String msg) {
        super(msg);
    }
}

 这里来说明一下：为什么节点的引用是节点类型？

首先，我们最开始在学习引用的时候，说过引用其实就是一个变量类型，用来存放地址。而在C语言中是用指针来存放地址，按照C语言的说法，节点的地址就得用节点类型的指针来接收。那么listNode 类型的 next，就得用 listNode 来接收（引用）。就好像，在 new 应该对象时，这个对象的地址会给到一个引用变量，而这个引用变量的类型就是 new 关键字后面的。例如：Person person = new Person();  。

双链表的学习，点我

上面这篇博文是关于链表的基础知识、链表的分类以及单链表的实现。都详细的进行了说明。

手动实现双链表的源码

public class MyLinkedList implements LinkedList {
    //创建一个节点内部类
    static class ListNode {
        int val;
        ListNode prev;
        ListNode next;

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

    // 头插
    @Override
    public void addFirst(int data) {
        // 创建一个新的节点
        ListNode newNode = new ListNode(data);
        // 先判断链表是否为空
        if (head == null) {
            head = newNode;
            last = newNode;
        }else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    @Override
    public void addLast(int data) {
        // 创建一个新的节点
        ListNode newNode = new ListNode(data);
        // 先判断链表是否为空
        if (head == null) {
            head = newNode;
            last = newNode;
        }else {
            last.next = newNode;
            newNode.prev = last;
            last = newNode;
        }
    }

    @Override
    public void addIndex(int data, int index) throws addIndexOfException {
        // 判断这个index是否合法
        if (index < 0 || index > size()) {
            // 抛异常
            throw new addIndexOfException("下标位置不合法异常！");
        }
        if (index == 0) {
            // 头插
            addFirst(data);
        } else if (index == size()) {
            // 尾插
            addLast(data);
        } else {
            // 创建一个新的节点
            ListNode newNode = new ListNode(data);
            ListNode cur = head;
            // 找到要插入的前一个位置
            while (index-1 > 0) {
                cur = cur.next;
                index--;
            }
            ListNode curNext = cur.next;
            cur.next = newNode;
            newNode.next = curNext;
            newNode.prev = cur;
            curNext.prev = newNode;
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if (head == null) {
            // 链表为空，就抛异常
            throw new LinkedListIsEmptyException("链表为空异常！");
        }else if (head.next == null) {
            // 链表里面只有一个元素
            if (head.val == key) {
                head = null;
                last = null;
                return;
            }else {
                throw new NotFindException("找不到要删除的数异常！");
            }
        }else {
            // 头删
            if (head.val == key) {
                head = head.next;
                return;
            } else if (last.val == key) {
                // 尾删
                last = last.prev;
                last.next = null;
                return;
            }
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    // 开始删除
                    ListNode curNext = cur.next;
                    cur.prev.next = curNext;
                    curNext.prev = cur.prev;
                    return;
                }
                cur = cur.next;
            }
            throw new NotFindException("找不到要删除的数异常！");
        }
    }

    @Override
    public void removeAllkey(int key) {
        if (head == null) {
            // 链表为空，就抛异常
            throw new LinkedListIsEmptyException("链表为空异常！");
        }else if (head.next == null) {
            // 链表里面只有一个元素
            if (head.val == key) {
                head = null;
                last = null;
                return;
            }else {
                throw new NotFindException("找不到要删除的数异常！");
            }
        }else {
            boolean flag = false;
            // 头删
            while (head.val == key) {
                flag = true;
                head = head.next;
                if (head == null) {
                    return;
                }
            }
            while (last.val == key) {
                // 尾删
                flag = true;
                last = last.prev;
                last.next = null;
            }
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    // 开始删除
                    flag = true;
                    ListNode curNext = cur.next;
                    cur.prev.next = curNext;
                    curNext.prev = cur.prev;
                }
                cur = cur.next;
            }
            if (!flag) {
                throw new NotFindException("找不到要删除的数异常！");
            }
        }
    }

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

    @Override
    public void clear() {
        // 暴力做法
        // head = last = null;

        // 温柔做法
        ListNode cur = head;
        while (cur != null) {
            // cur.val = null;
            cur.prev = null;
            ListNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = last = null;
    }

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

 addlndexOfException异常：

public class addIndexOfException extends RuntimeException {
    public addIndexOfException(String msg) {
        super(msg);
    }

    public addIndexOfException() {
        super();
    }
}

LinkedListlsEmptyException异常：

public class LinkedListIsEmptyException extends RuntimeException {
    public LinkedListIsEmptyException(String msg) {
        super(msg);
    }
    public LinkedListIsEmptyException() {
        super();
    }
}

 NotFindException异常：

public class NotFindException extends RuntimeException {
    public NotFindException(String msg) {
        super(msg);
    }
    public NotFindException() {
        super();
    }
}

单链表和双链表在代码上，总体来说，大差不差。

分析 LinkedList 的源码 

LinkedList的底层使用了双向链表 

LinkedList的使用 

构造方法与 ArrayList 差不多，只有一个无参的和一个带参数的。带参的类型是实现了Collection接口就行。

常用方法 

方法	说明
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的所有元素
E remove(int index)	删除 index位置元素
boolean remove(Object o)	删除遇到的第一个o
E get(int index)	获取下标index 位置元素
E set(int index, E element)	将下标index位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断o是否在链表中
int indexOf(Object o)	返回第一个o所在下标
int lastlndexOf(Object o)	返回最后一个o的下标
List<E> subList(int fromlndex, int tolndex)	截取部分list

同样这里 subList 的截取不会产生新的对象。

其遍历方式和 ArrayList 是一样的。

ArrayList和LinkedList的区别

区别	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持0(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

好啦！本期 数据结构之LinkedList与链表（上）的学习之旅就到此结束啦！我们下一期再一起学习吧！