欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

双向链表在java中的应用举例-LinkedList

程序员文章站 2022-07-14 08:34:29
...

双向链表在java中的应用举例-LinkedList

复习了链表,作为一种高效的存储数据的方式

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

这里LinkedList 继承于AbstractSequentialList的双向链表。
同时实现了List接口可以通过指向List进行实例化,能进行队列操作。
实现了Deque接口,也可以当作双端队列来使用。
Cloneable可以实现克隆操作。
java.io.Serializable表明该类可以进行序列化。

构造函数

 public LinkedList() {
    }


    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

可以看到里面提供一个空的构造函数和一个可以赋值的实现了collecton接口的集合
双向链表在java中的应用举例-LinkedList

可以看到collection是集合的基本类,set,list都继承了collection接口,所以,可以将实现了上述的接口的类添加进去。

接下来 看一下addall方法

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;     //求出新加入的数组的大小
        if (numNew == 0)
            return false;

        Node<E> pred, succ;       //pred为插入位置的头结点,succ为后节点
        if (index == size) {      //如果直接是在最后进行插入
            succ = null;          //将尾节点设置尾空,本来是就是空,这个时候不需要尾节点进行作,
            //当直接进行尾插的时候,仅仅需要一个节点就可以完成
            pred = last;          //将头结点设置到尾部,方便插入
        } else {
            succ = node(index);   //设置尾节点为具体的位置
            pred = succ.prev;      //设置为succ的前置节点
        }

        for (Object o : a) {       //循环加入节点
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);     //因为是尾插,后置节点一直为空
            if (pred == null)
                first = newNode;                           //头结点为空,在第一次插入时候出现
            else
                pred.next = newNode;                       //如果不是第一次 插入,循环尾插
            pred = newNode;
        }

        if (succ == null) {                               //如果是插入的位置在尾部,直接将last
        //设置为pred 指向尾部,这里last的next为空
            last = pred;
        } else {
            pred.next = succ;     //如果不是插入在尾部,需要对头结点和尾节点进行链接,这里pre已经
            //到达了尾部
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

这里要指出的是Node是其中的一个类部类,创建双向指针的内部类,代码如下,可以通过构造方法设置他的指向,也应该为了配合链表特性没有用标准 的set get方法。

 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

add方法

public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

同理,上面的add方法也是通过尾插的方法将其插入尾部

同时类中还封装了其他很多的方法,本篇主要对LinkedList中的链表方法进行讲解,其他的部分读者可以自行参考源码。
如果有问题欢迎指正。

相关标签: java