[Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.ArrayList的缺点

上篇文章我们已经对顺序表进行了实现,并且对ArrayList进行了使用,我们知道ArrayList底层是使用数组实现的.
由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

2.链表

2.1 链表的概念与结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的.就像一列动车一样.
[Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现,Collection与数据结构,数据结构,链表

通过上图我们可以看到,一个链表中有一节一节的"车厢",还有中间的"链条".我们称每一节"车厢"为结点,我们可以看到每一个结点中有下一个结点的地址,链表就是通过存储节点的地址来连接起来的,还有该结点的值.上面就是我们需要重点掌握的一种链表类型,叫做单向无头非循环链表.其实链表还有好多类型,下面我们来展示.

2.2 链表的类型

链表有以下几种性质:有头/无头,单向/双向,循环/非循环

有头/无头

它们的区别就是,有头链表的head永远指向一个固定的结点,而无头链表的head永远在改变.
单向/双向

[Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现,Collection与数据结构,数据结构,链表
3. 循环/非循环

上面几种性质排列组合可以得到许多中链表的类型,这里我们重点掌握2中即可,一种是单向无头非循环,它在笔面试中经常出现,另一种是是无头双向非循环链表,Java中的LinkedList底层就是通过它来实现的.

3. 单向无头非循环链表实现

下面是要实现的接口,即链表中的常用方法:

public interface ILinkedList {
    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();

}

下面我们来实现这些方法:

public class MyLinkedList implements ILinkedList {
    static class Node{
        public int val;
        public Node next = null;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node head = null;

    /**
     * 创建默认链表
     */
    public void createDeafultLinkedList(){
        Node node = new Node(23);
        this.head = node;
        Node node1 = new Node(34);
        node.next = node1;
        Node node2 = new Node(45);
        node1.next = node2;
        Node node3 = new Node(56);
        node2.next = node3;
        Node node4 = new Node(67);
        node3.next = node4;
    }

    /**
     * 在链表头部添加新的结点
     * @param data
     */
    @Override
    public void addFirst(int data) {
        Node node = new Node(data);
//        if(head == null){
//            head = node;
//        }else {
//            node.next = head;
//            head = node;
//        }
        //上面的代码其实没必要验证链表是否为空,head为null赋值过去还是null
        node.next = this.head;
        this.head = node;
    }

    /**
     * 在尾部添加新的结点
     * @param data
     */
    @Override
    public void addLast(int data) {
        Node node = new Node(data);
        Node cur = this.head;
        if (this.head == null){
            this.head = node;
        }else {
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    /**
     * 在指定位置添加结点
     * @param index
     * @param data
     */
    @Override
    public void addIndex(int index, int data) {
        if (index > size() || index < 0){
            throw new IndexExeption("下标有误");
        }
        Node node = new Node(data);
        if (this.head == null){
            this.head = node;
            return;//记得返回,不然会执行中间插入的代码
        }
        if (index == 0){//在链表头添加
            addFirst(node.val);
            return;
        }
        if (index == size()){//在链表尾部添加
            addLast(node.val);
            return;
        }
        //在中部添加
        Node cur = this.head;
        int count = 0;
        while (count != index-1){//寻找cur的前一个结点
            cur = cur.next;
            count++;
        }
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 检测链表中是否含有指定的值
     * @param key
     * @return
     */
    @Override
    public boolean contains(int key) {
        Node cur = this.head;
        while (cur != null){//先遍历链表
            if(cur.val == key){//在遍历的过程中如果等于,返回true
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 移除遇到的第一个值为key的元素
     * @param key
     */
    @Override
    public void remove(int key) {
        if (this.head == null){
            return;
        }
        if (head.val == key){
            head = head.next;
            return;
        }
        Node cur = findPreNode(key);//需要找到前一个结点才可以删除
        if (cur == null){//没找到要删除的结点
            return;
        }
        cur.next = cur.next.next;
    }
    private Node findPreNode(int key){//找到要删除结点的前一个结点
        Node cur = this.head;
        while (cur.next != null){//这里必须写成next不等于null,否则下面可能会出现空指针异常
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 移除所有符合值为key的结点
     * @param key
     */

    @Override
    public void removeAllKey(int key) {
        if (this.head == null){
            return;
        }
        Node pre = this.head;
        Node cur = this.head.next;
        //先不要管头结点,先删中间的
        while(cur != null){
            if (cur.val == key){
                pre.next = cur.next;
            }else {
                pre = pre.next;//若该结点不是要删除的结点,pre往后走
            }
            cur = cur.next;
        }
        //所有的都删完了,删除头结点
        if (head.val == key){
            head = head.next;
        }
    }

    /**
     * 计算链表大小
     * @return
     */
    @Override
    public int size() {
        int count = 0;
        Node cur = this.head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 清空链表
     */
    @Override
    public void clear() {
        head = null;//为被引用的结点会被JWM回收
    }

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

    /**
     * 从指定位置开始打印链表
     * @param node
     */
    public void display(Node node) {
        Node cur = node;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

}

上面有几个问题需要注意

在中间插入元素的时候先要进行后链接,在进行前链接,如果先进行前链接,cur的下一个结点的地址就会丢失
在删除所有值为key的结点的时候,先删除head后符合条件的结点最后再处理head.

下面是对上述问题的动态演示:

[插入结点错误演示]

插入中间节点(错误)

[插入结点正确演示]

插入中间结点(正确)

[删除所有key结点]

删除所有key结点

下面我们对上述实现的方法进行测试:

**
 * 开始测试
 */
public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.createDeafultLinkedList();
        myLinkedList.addFirst(11);
        myLinkedList.addLast(88);
        myLinkedList.display();
        System.out.println(myLinkedList.size());
        myLinkedList.addIndex(2,33);
        myLinkedList.display();
        System.out.println(myLinkedList.contains(11));
        System.out.println(myLinkedList.contains(12));
        myLinkedList.addIndex(1,23);
        myLinkedList.addIndex(1,23);
        myLinkedList.addIndex(1,23);
        myLinkedList.display();
        myLinkedList.remove(23);
        myLinkedList.display();
        myLinkedList.removeAllKey(23);
        myLinkedList.display();
        myLinkedList.clear();
        myLinkedList.display();
    }
}