当前位置：首页 > article >正文

LinkedList底层结构

article 2025/2/23 20:56:51

LinkedList基本介绍

LinkedList底层操作机制

双向列表的模拟实现

LinkedList源码分析

add源码分析：

remove源码分析：

ArrayList和LirnkedList比较

LinkedList基本介绍

1)LinkedList底层实现了双向链表和双端队列特点

2)可以添加任意元素(元素可以重复)，包括null

3)线程不安全，没有实现同步

LinkedList底层操作机制

1.LinkedList底层维护了一个双向链表.

2)LinkedList中维护了两个属性first和last分别指向首节点和尾节点

3)每个节点(Node对象)，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表.

4)所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

双向列表的模拟实现

代码演示：

package idea.chapter14.list_;

/**
 * 模拟双向列表
 */
public class LinkedList01 {
    public static void main(String[] args) {

        //创建三个节点
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node mary = new Node("mary");

        jack.next = tom;
        tom.next = mary;

        mary.pre = tom;
        tom.pre = jack;

        Node first = jack;//让first引用指向jack,就是双向链表的头结点   就是头指针
        Node last = mary;//让last引用指向mary,就是双向链表的尾结点     就是尾指针

        //遍历这个列表
        while (true) {
            //判断如果当前first指向的节点如果是null的话，那么就跳出循环
            if (first == null) {
                break;
            }
            //然后输出first的内容
            System.out.println(first);
            //让first指向下一个节点
            first = first.next;
        }

        //插入一个节点
        Node smith = new Node("smith");
        tom.next = smith;
        smith.next = mary;
        mary.pre = smith;
        smith.pre = tom;

        //让first重新指向第一个节点，因为我们在上面遍历的时候，first已经指向的最后一个节点了，所以在这里进行遍历的时候，我们要重新将first指向第一个节点去
        first = jack;
        while (true) {
            if (first == null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }
    }
}


//定义一个Node 类，Node 对象 表示双向链表的一个结点
class Node {
    public Object item; //真正存放数据
    public Node next; //指向后一个结点
    public Node pre; //指向前一个结点

    public Node(Object item) {
        this.item = item;
    }

    @Override
    public String toString() {
        return "Node name=" + item;
    }
}

LinkedList源码分析

源码分析：

add源码分析：

       /* 1. LinkedList linkedList = new LinkedList();
              public LinkedList() {

              }
           2. 这时 linkeList 的属性 first = null  last = null
           3. 执行 添加
               public boolean add(E e) {
                    //这里就是真正添加的方法
                    linkLast(e);
                    return true;
                }
            4.将新的结点，加入到双向链表的最后


//在添加第二个元素时 final Node<E> l = last;//此时last还是空
//紧接着创建了一个新的节点 final Node<E> newNode = new Node<>(l, e, null); 此时l作为指向第一个节点的引用赋给了第二个节点pre的位置
//这个时候新节点的pre就指向了，第一个节点，
// 紧接着last = newNode;就是让last指向新的节点
//这个时候判断l是否等于空很显然，l指向了第一个节点，此时不为空
//因此执行l.next=new newNode 也就是让l执行新节点的next因为在这个之前l一直指向的就是第一个节点

             void linkLast(E e) {
                //在第一次进来的时候，因为last等于null,所以l此时就是null
                final Node<E> l = last;//此时last是空让l指向null
                //然后这里就创建了一个节点，注意此时，他将l放在了创建出来的新节点的pre的位置，所以此时新节点的pre就指向了第一个节点
                final Node<E> newNode = new Node<>(l, e, null);
                //然后让last指向了新的节点
                last = newNode;
                //这里判断l是否为null 此时l肯定为null 所以让first也指向了创建出来的新节点
                if (l == null)
                    first = newNode;
                else
                    l.next = newNode;
                size++;
                modCount++;
            }

         */

remove源码分析：

        /*
          源码 linkedList.remove(); // 这里默认删除的是第一个结点
          1. 执行 removeFirst
            public E remove() {
                return removeFirst();
            }
         2. 执行
            public E removeFirst() {
                final Node<E> f = first;
                if (f == null)
                    throw new NoSuchElementException();
                return unlinkFirst(f);
            }
          3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉


//在删除元素的时候会先进行把你要删除的那个节点中的元素保存到一个element中，也就时这一句话final E element = f.item;
//紧接着就是final Node<E> next = f.next;让next指向下一个节点
//然后就是把第一个节点保存元素的地方置空，把第一个节点指向下一个节点也置空    f.item = null; f.next = null; // help GC  也就是这两句话
//help GC的意思是，把第一个节点置空了，系统会回收
//first = next;然后就是让first指向下一个节点
//这个时候判断next是不是null。很显然next不为空因此执行next.prev = null;把next指向前一个节点的pre也置空，这样也就完成了删除
//size表示的当前海还剩下了多少个元素  modCount表示当前操作过几次


            private E unlinkFirst(Node<E> f) {
                // assert f == first && f != null;
                //先将节点中的内容存放到item中
                final E element = f.item;
                然后让next指向下一个节点
                final Node<E> next = f.next;
                f.item = null;
                f.next = null; // help GC
                first = next;
                if (next == null)
                    last = null;
                else
                    next.prev = null;
                size--;
                modCount++;
                //最后返回的是你删除的那个元素
                return element;
            }
         */

package idea.chapter14.list_;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * LinkedList的源码分析
 */
@SuppressWarnings({"all"})
public class LinkedListCRUD {
    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("linkedList=" + linkedList);

        //演示一个删除结点的
        linkedList.remove(); // 这里默认删除的是第一个结点
        //linkedList.remove(2);

        System.out.println("linkedList=" + linkedList);

        //修改某个结点对象
        linkedList.set(1, 999);
        System.out.println("linkedList=" + linkedList);

        //得到某个结点对象
        //get(1) 是得到双向链表的第二个对象
        Object o = linkedList.get(1);
        System.out.println(o);//999

        //因为LinkedList 是 实现了List接口, 遍历方式
        System.out.println("===LinkeList遍历迭代器====");
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next = iterator.next();
            System.out.println("next=" + next);

        }

        System.out.println("===LinkeList遍历增强for====");
        for (Object o1 : linkedList) {
            System.out.println("o1=" + o1);
        }
        
        System.out.println("===LinkeList遍历普通for====");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }


        //源码分析
        /* 1. LinkedList linkedList = new LinkedList();
              public LinkedList() {
              
              }
           2. 这时 linkeList 的属性 first = null  last = null
           3. 执行 添加
               public boolean add(E e) {
                    //这里就是真正添加的方法
                    linkLast(e);
                    return true;
                }
            4.将新的结点，加入到双向链表的最后


//在添加第二个元素时 final Node<E> l = last;//此时last还是空
//紧接着创建了一个新的节点 final Node<E> newNode = new Node<>(l, e, null); 此时l作为指向第一个节点的引用赋给了第二个节点pre的位置
//这个时候新节点的pre就指向了，第一个节点，
// 紧接着last = newNode;就是让last指向新的节点
//这个时候判断l是否等于空很显然，l指向了第一个节点，此时不为空
//因此执行l.next=new newNode 也就是让l执行新节点的next因为在这个之前l一直指向的就是第一个节点

             void linkLast(E e) {
                //在第一次进来的时候，因为last等于null,所以l此时就是null
                final Node<E> l = last;//此时last是空让l指向null
                //然后这里就创建了一个节点，注意此时，他将l放在了创建出来的新节点的pre的位置，所以此时新节点的pre就指向了第一个节点
                final Node<E> newNode = new Node<>(l, e, null);
                //然后让last指向了新的节点
                last = newNode;
                //这里判断l是否为null 此时l肯定为null 所以让first也指向了创建出来的新节点
                if (l == null)
                    first = newNode;
                else
                    l.next = newNode;
                size++;
                modCount++;
            }

         */

        /*
          源码 linkedList.remove(); // 这里默认删除的是第一个结点
          1. 执行 removeFirst
            public E remove() {
                return removeFirst();
            }
         2. 执行
            public E removeFirst() {
                final Node<E> f = first;
                if (f == null)
                    throw new NoSuchElementException();
                return unlinkFirst(f);
            }
          3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉


//在删除元素的时候会先进行把你要删除的那个节点中的元素保存到一个element中，也就时这一句话final E element = f.item;
//紧接着就是final Node<E> next = f.next;让next指向下一个节点
//然后就是把第一个节点保存元素的地方置空，把第一个节点指向下一个节点也置空    f.item = null; f.next = null; // help GC  也就是这两句话
//help GC的意思是，把第一个节点置空了，系统会回收
//first = next;然后就是让first指向下一个节点
//这个时候判断next是不是null。很显然next不为空因此执行next.prev = null;把next指向前一个节点的pre也置空，这样也就完成了删除
//size表示的当前海还剩下了多少个元素  modCount表示当前操作过几次


            private E unlinkFirst(Node<E> f) {
                // assert f == first && f != null;
                //先将节点中的内容存放到item中
                final E element = f.item;
                然后让next指向下一个节点
                final Node<E> next = f.next;
                f.item = null;
                f.next = null; // help GC
                first = next;
                if (next == null)
                    last = null;
                else
                    next.prev = null;
                size--;
                modCount++;
                //最后返回的是你删除的那个元素
                return element;
            }
         */
    }
}