Java面向对象之LinkedList 底层结构及ArrayList 和 LinkedList 比较

• • • 1、linkedList 底层结构
    • • 1.1、linkedList 的全面说明
      • 1.2、linkedList 的底层操作机制
      • 1.3、linkedList 的增删改查
      • 1.4、linkedList 源码解析
      • • 1.4.1、linkedList 添加源码
        • 1.4.2、linkedList 删除源码
    • 2、ArrayList 和 linkedList 比较

1. linkedList底层实现了双向链表和双端队列特点
2. 可以添加任意元素（元素可以重复），包括null
3. 线程不安全，没有实现同步

package list_;

public class linkedList01 {
    public static void main(String[] args) {
        // 模拟一个简单的双向链表
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node lily = new Node("lily");

        // 连接三个结点, 形成双向链表
        // jack -> tom -> lily
        jack.next = tom;
        tom.next = lily;
        // lily -> tom -> jack
        lily.pre = tom;
        tom.pre = jack;

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

        // 从头到尾进行遍历
        System.out.println("===从头到尾进行遍历===");
        while (true) {
            if (first == null) {
                break;
            }
            // 输出first信息
            System.out.println(first);
            first = first.next;
            
        }

        // 从尾到头的遍历
        System.out.println("===从尾到头的遍历===");
        while (true) {
            if (last == null) {
                break;
            }
            // 输出 last信息
            System.out.println(last);
            last = last.pre;
            
        }

        // 链表的添加对象/数据，非常方便
        // 要求在 tom 和 lily之间, 插入一个对象 smith
        // 先创建一个 Node 结点, name 就是 smith
        Node smith = new Node("smith");
        // 下面就把 smith 加入到双向链表了
        smith.next = lily;
        smith.pre = tom;
        tom.next = smith;
        lily.pre = smith;

        // 让 first 再次指向 jack
        first = jack;  // 让 first 引用指向 jack, 就是双向链表的头结点

        // 从头到尾进行遍历
        System.out.println("===从头到尾进行遍历===");
        while (true) {
            if (first == null) {
                break;
            }
            // 输出first信息
            System.out.println(first);
            first = first.next;
            
        }

        // 让 last 再次指向 lily
        last = lily;
        // 从尾到头的遍历
        System.out.println("===从尾到头的遍历===");
        while (true) {
            if (last == null) {
                break;
            }
            // 输出 last信息
            System.out.println(last);
            last = last.pre;
            
        }
    }
}

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

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

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

package list_;

import java.util.Iterator;
import java.util.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=[1, 2, 3]

        // 删除结点
        linkedList.remove();  // 这里默认删除的是第一个结点
        System.out.println("linkedList=" + linkedList);  // linkedList=[2, 3]
        linkedList.remove(1);  // ()内放的是下标index
        System.out.println("linkedList=" + linkedList);  // linkedList=[2]

        // 修改某个结点对象
        linkedList.set(0, 999);  // 将第一个参数index 的值改成 第二个参数对应的值, index下标不存在 报错
        System.out.println("linkedList=" + linkedList);  // linkedList=[999]

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

        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("linkedList=" + linkedList);  // linkedList=[999, 1, 2, 3]

        // 因为 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) {  // 快捷键: I + tab
            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, 见图1

3. 执行 添加	
   public boolean add(E e) {
       linkLast(e);
       return true;
   }
   
4.将新的结点, 加入到双向链表的最后
  void linkLast(E e) {
      final Node l = last;
      final Node newNode = new Node<>(l, e, null);
      last = newNode;
      if (l == null)
          first = newNode;
      else
          l.next = newNode;
      size++;
      modCount++;
  }

图1：

linkedList.remove();  // 这里默认删除的是第一个结点
   
1. 执行 removeFirst
   public E remove() {
       return removeFirst();
   }
2. 执行
   public E removeFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
   }
3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉
   private E unlinkFirst(Node f) {
       // assert f == first && f != null;
       final E element = f.item;
       final Node 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;
   }