HelloWorld
登录

LinkedList

Stella981

2021-10-11

1581 0 0

Base：JDK1.8

1、LinkedList

LinkedList 也是一个比较常见的数据结构，链表。在C/C++ 中，链表也是一个典型的线性结构，链表分为单向跟双向的两种链表。在java里面的LinkedList是一个双向的链表。

链表最好的好处就在于来一个数据加一个长度，没有多余的冗余， 也是支持存储各种对象的（最好使用泛型）。

2、继承的类and实现的接口

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

2.1、AbstractSequentialList

2.2、List

跟ArrayList实现的同一个接口，因此就不贴了。

2.3、Dequen

deque 即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

这个后续学队列再去详细的介绍。

2.4、Cloneable、java.io.Serializable

跟ArrayList一样，都是支持克隆和序列化的。

3、LinkedList中的成员变量、数据结构、常用方法

3.1、成员变量

transient int size = 0;

用来记录 链表的大小，同样是transient的。

transient Node<E> first;

表示头结点。

transient Node<E> last;

表示最后一个节点。

3.2、数据结构

因为链表也是一个典型的线性结构，跟数组相似，但是也有不同，因为链表在逻辑地址（我们脑海中）是一个连续的地址，而在物理地址（电脑内存中）中却不是连续的一块，而是一个点，一个点的，这个节点持有上个节点，和下个节点的引用，如图：

因为逻辑地址并不要求是一块内存，因此链表在这方面还是要优于数组的。

但是正是不需要内存连续，因此要额外的需要持有上一个节点和下一个节点的引用。单个内存的开销变大。

1    private static class Node<E> {
2        //内部类
3        //数据节点
4        E item;
5        //下一个节点的引用
6        Node<E> next;
7        //上一个节点的引用
8        Node<E> prev;
9        //构造方法
10        Node(Node<E> prev, E element, Node<E> next) {
11            this.item = element;
12            this.next = next;
13            this.prev = prev;
14        }
15    }

这是LinkedList中的内部类，Node ，每add一个数据就会有一个Node对象，每一个节点都有前后两个节点的引用，这就形成了一个双向链表。

跟ArrayList 相同的，Node 节点也是 transient 的修饰的，因此，后面也会重写private void writeObject(java.io.ObjectOutputStream s) 和 private void readObject(java.io.ObjectInputStream s) 这两个方法。目的跟ArrayList应该是一样的。

3.3 常用重要方法

3.3.1 构造方法

3.3.1.1 无参构造

1/**
2     * Constructs an empty list.
3     */
4    public LinkedList() {
5    }

不解释。

3.3.1.2 参数为   Collection 的构造方法

1    public LinkedList(Collection<? extends E> c) {
2        this();
3        //添加
4        addAll(c);
5    }

这个方法可以直接将已经存在的Collection 转换为一个LinkList 包括ArrayList 还有其他 子类。

----------------------

在这里发现，LinkedList的构造方法是没有指定长度的构造方法，这是跟数组的一个比较 重要的区别（这不是废话吗。。。。。。）

---------------------

3.3.2 add

3.2.2.1 public boolean add(E e)

1public boolean add(E e) {
2         //调用另外一个方法
3        linkLast(e);
4        return true;
5    }

由于add方法内部是调用的另外一个方法，因此贴出另外的方法。

1/**
2     * Links e as last element.
3     */
4    void linkLast(E e) {
5        //last 是记录的最后一个元素
6        final Node<E> l = last;
7        //new 一个Node 的节点
8        final Node<E> newNode = new Node<>(l, e, null);
9        //last更新为新生成的
10        last = newNode;
11        //如果last为null证明这是第一次添加，那么他就是第一个，也是最后一个。
12        if (l == null)
13            first = newNode;
14        else
15            l.next = newNode;
16        //大小+1
17        size++;
18        //fail-fast 机制
19        modCount++;
20    }

有这个方法名字就可以很直白的看出来，是添到了链表的尾部。

其中的 new Node<>(l,e,null) 可以去看上面的 贴出来的Node的构造方法，

1Node(Node<E> prev, E element, Node<E> next) {
2            this.item = element;
3            this.next = next;
4            this.prev = prev;
5        }

之前的last设为 新的 prev，next 设置为null   item 设置为存储的数据。

3.2.2.2 public void add(int index, E element)

1    public void add(int index, E element) {
2        //下标检测，是否超出
3        checkPositionIndex(index);
4        //如果位置正好等于 size ，就直接插入到最后
5        if (index == size)
6            linkLast(element);
7        else
8            //插入到指定位置
9            linkBefore(element, node(index));
10    }

由于链表也是一个线性结构，因此也支持够插入到指定位置。

1void linkBefore(E e, Node<E> succ) {
2        // assert succ != null;
3        //插入之前的index 位置上的元素的 前一个元素
4        final Node<E> pred = succ.prev;
5        final Node<E> newNode = new Node<>(pred, e, succ);
6        //将原 index 位置上的元素的前一个 设置为新的节点 
7        succ.prev = newNode;
8        if (pred == null)
9            //如果此节点的前一个是null，意味着插入的是首个位置
10            first = newNode;
11        else
12            //前 index 位置的元素的前一个的 下一个引用，设置为新节点
13            pred.next = newNode;
14        size++;
15        modCount++;
16    }

画一个图应该是更好理解。

------------------------------------------------

灵魂画手：

大体的分为三步， 如果插入的位置是 0 ，跟这个差不多。

------------------------------------------------------

3.2.2.3 其他的add

public void addFirst(E e)

1public void addFirst(E e) {
2        linkFirst(e);
3    }
4
5 private void linkFirst(E e) {
6        final Node<E> f = first;
7        final Node<E> newNode = new Node<>(null, e, f);
8        first = newNode;
9        if (f == null)
10            last = newNode;
11        else
12            f.prev = newNode;
13        size++;
14        modCount++;
15    }

这个从名字就很好看出来，就是添加到位置 0。

不过为什么不用add(0,e)，而是再写一个方法呢？

----------------------------------------------------------

public void addLast(E e)

1  public void addLast(E e) {
2        linkLast(e);
3    }
4
5    void linkLast(E e) {
6        final Node<E> l = last;
7        final Node<E> newNode = new Node<>(l, e, null);
8        last = newNode;
9        if (l == null)
10            first = newNode;
11        else
12            l.next = newNode;
13        size++;
14        modCount++;
15    }

这两个方法，大同小异吧，具体实现也是差不多的，不过就是明明有了add具体位置插入，为什么不用这个方法，而是另外再写呢？

public boolean addAll(Collection<? extends E> c)

1  public boolean addAll(Collection<? extends E> c) {
2        return addAll(size, c);
3    }

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

1    public boolean addAll(int index, Collection<? extends E> c) {
2        checkPositionIndex(index);
3
4        Object[] a = c.toArray();
5        int numNew = a.length;
6        if (numNew == 0)
7            return false;
8
9        Node<E> pred, succ;
10        if (index == size) {
11            succ = null;
12            pred = last;
13        } else {
14            succ = node(index);
15            pred = succ.prev;
16        }
17
18        for (Object o : a) {
19            @SuppressWarnings("unchecked") E e = (E) o;
20            Node<E> newNode = new Node<>(pred, e, null);
21            if (pred == null)
22                first = newNode;
23            else
24                pred.next = newNode;
25            pred = newNode;
26        }
27
28        if (succ == null) {
29            last = pred;
30        } else {
31            pred.next = succ;
32            succ.prev = pred;
33        }
34
35        size += numNew;
36        modCount++;
37        return true;
38    }

这两个 方法是将 Collection 的某个集合里面的全部数据放入到 LinkedList 中，感觉用的不是很多，问的也不会很多，我也没注意过，不看了。

--------------------------------------------------------

3.3.3 remove

 public E remove(int index)

1    public E remove(int index) {
2        //边界检测
3        checkElementIndex(index);
4          //执行删除的函数
5        return unlink(node(index));
6    }
7
8    Node<E> node(int index) {
9        // assert isElementIndex(index);
10          //如果index 是小于 size/2的 就从前找
11        if (index < (size >> 1)) {
12            Node<E> x = first;
13            for (int i = 0; i < index; i++)
14                x = x.next;
15            return x;
16        } else {
17            //否则从后找
18            Node<E> x = last;
19            for (int i = size - 1; i > index; i--)
20                x = x.prev;
21            return x;
22        }
23    }

上面你这个函数就是 node(index) 的方法，可以看出他是返回了 index位置上的 node的引用，因为链表在内存中是不连续的，所以只能通过遍历链表去查找 对应的数据，

这个判断 index<(seze>>1) 的思想是 二分法的思想，将整个链表分为2份，看从哪边近，就从哪边开始，这也是双链表的优点，如果是单链表，就只能从前往后遍历了。

1 E unlink(Node<E> x) {
2        // assert x != null;
3         //首先记录三个节点，当前的，前一个，后一个，每个对结构有调整的（add，remove ）
4         // 一般第一步 都是记录这三个
5        final E element = x.item;
6        final Node<E> next = x.next;
7        final Node<E> prev = x.prev;
8        //如果前一个是null，就意味着删除的是first节点
9        if (prev == null) {
10            //直接将 first指向 第二个
11            first = next;
12        } else {
13            //如果不是first元素，将要删除的前一个元素的 next 指向 当前元素的下一个
14            prev.next = next;
15           //将当前的前一个元素置空。
16            x.prev = null;
17        }
18        //意味删除的是最后一个节点
19        if (next == null) {
20           //last 前移一个
21            last = prev;
22        } else {
23           // 否则将下一个节点 的 前一个引用 设为 当前节点的前一个
24            next.prev = prev;
25           //将 当前节点的 下一个置空 
26            x.next = null;
27        }
28       //数据置空
29        x.item = null;
30        size--;
31        modCount++;
32        return element;
33    }

---------------------------------

来个图：

突然感觉自己很有画图天赋。。。。23333333

-------------------------------------------

public boolean remove(Object o)

1    public boolean remove(Object o) {
2        if (o == null) {
3            //如果 需要删除的对象是null 
4            for (Node<E> x = first; x != null; x = x.next) {
5                if (x.item == null) {
6                    unlink(x);
7                    return true;
8                }
9            }
10        } else {
11          //对象不是null 就是用 equals方法 
12            for (Node<E> x = first; x != null; x = x.next) {
13                if (o.equals(x.item)) {
14                    unlink(x);
15                    return true;
16                }
17            }
18        }
19        return false;
20    }

这个其实只是分了 null和非null 两种情况，null 使用== ，非null 使用 equals 方法进行比较。

其中调用的删除的方法 还是 unlink(x) 。

时刻记得，链表虽然是一个线性表，但是无法像 数组那样，直接下标偏移量 找到删除的元素，这个必须需要进行一个 遍历，将整个链表 遍历完成。

同样的，这里删除同样要避免删除的时候，你想删除的如果是int 类型的数据，切记要转换为 包装类，否则调用的方法是remve(int)。

---------------------------------------------

其他的remove方法

public E removeFirst()

public E removeLast()

----------------------------------------------

3.3.4 get

1    public E get(int index) {
2        checkElementIndex(index);
3        return node(index).item;
4    }

整个get方法很少，判断是否越界，然后返回 index 位置节点的 item 。

--------------------

其他 get方法

public E getFirst()

public E getLast()

------------------------

其他类似 get 方法

public E peek()

1 /**
2     * Retrieves, but does not remove, the head (first element) of this list.
3     *
4     * @return the head of this list, or {@code null} if this list is empty
5     * @since 1.5
6     */
7 public E peek() {
8        final Node<E> f = first;
9        return (f == null) ? null : f.item;
10    }

public E element()

1   /**
2     * Retrieves, but does not remove, the head (first element) of this list.
3     *
4     * @return the head of this list
5     * @throws NoSuchElementException if this list is empty
6     * @since 1.5
7     */
8    public E element() {
9        return getFirst();
10    }
11
12  public E getFirst() {
13        final Node<E> f = first;
14        if (f == null)
15            throw new NoSuchElementException();
16        return f.item;
17    }

 public E poll()

1 /**
2     * Retrieves and removes the head (first element) of this list.
3     *
4     * @return the head of this list, or {@code null} if this list is empty
5     * @since 1.5
6     */
7    public E poll() {
8        final Node<E> f = first;
9        return (f == null) ? null : unlinkFirst(f);
10    }

这三个方法都是返回first  ，不过第1、3方法是 如果 first 是 null 就返回null ，第2个方法内部调用的是getFirst(),这个方法：如果是空，就 抛出异常。

1、2两个方法只是返回，不删除元素，3方法是返回切删除了元素。

这里面有很多类似的方法，就不贴了，贴了浪费流量。

3.2.5 contains

public boolean contains(Object o)

1public boolean contains(Object o) {
2        return indexOf(o) != -1;
3    }

这个是是否包含 某个元素。需要传入的是对象。

3.3 其他方法

 private void writeObject(java.io.ObjectOutputStream s)

private void readObject(java.io.ObjectInputStream s)

具体代码不贴了，感觉这个LinkedList写的有点啰嗦了。

public Object[] toArray()

public <T> T[] toArray(T[] a)

-----------------------------------------------------------------------------

不保证代码完全正确，也不保证代码是最优。

仅仅是根据自己的理解，写出来直观的代码，方便理解。

错误请指出，感激不尽！

点赞
收藏

评论区

加载中...

相关推荐

MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1

文章目录问题用navicat导入数据时，报错：原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等，这样可以更容易地在不同的环境中使用MySQL。全局s

Oracle 分组与拼接字符串同时使用

SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(

MySQL部分从库上面因为大量的临时表tmp_table造成慢查询

背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_

皕杰报表之UUID

​在我们用皕杰报表工具设计填报报表时，如何在新增行里自动增加id呢？能新增整数排序id吗？目前可以在新增行里自动增加id，但只能用uuid函数增加UUID编码，不能新增整数排序id。uuid函数说明：获取一个UUID，可以在填报表中用来创建数据ID语法：uuid()或uuid(sep)参数说明：sep布尔值，生成的uuid中是否包含分隔符''，缺省为

手写Java HashMap源码

HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22

2020年前端实用代码段，为你的工作保驾护航

有空的时候，自己总结了几个代码段，在开发中也经常使用，谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )