B站 韩顺平 老师课程的笔记

LinkedList

基本介绍

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

LinkedList 底层结构

1. 底层维护了一个双向链表
2. 维护了两个属性first和last分别指向 首节点和尾节点
3. 每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表。
4. 所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高
5. 模拟一个简单的双向链表

package com.list_;

import jdk.nashorn.internal.objects.annotations.Constructor;

public class LinkedList_01 {
public static void main(String[] args) {
   //模拟一个简单的双向链表(只是最简单的)

   //先创建三个对象
   Node jack = new Node("jack");
   Node niuren = new Node("牛人");
   Node tom = new Node("tom");

   //将三个对象链接起来成为双向链表
   //先形成jack->tom->niuren的单向链表
   jack.next = tom;
   tom.next = niuren;
   //在形成jack<-tom<-niuren的链表，相当于就是双向了
   niuren.pre = tom;
   tom.pre = jack;

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

   //演示从头到尾遍历
   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和niuren之间
   Node smith = new Node("smith");
   tom.next = smith;
   smith.next = niuren;
   niuren.pre = smith;
   smith.pre = tom;
   //遍历输出，就只展示从头到尾了，从尾到头很类似
   //之前的first已经移动过了，所以先要再次指向头部（jack）
   System.out.println("====插入新结点后遍历====");
   first = jack;
   while(true){
       if(first == null){
           break;
       }
       System.out.println(first);
       first = first.next;
   }

   //演示删除结点
   //删除tom
   jack.next = smith;
   smith.pre = jack;
   tom = null;
   //遍历输出，就只展示从头到尾了，从尾到头很类似
   //之前的first已经移动过了，所以先要再次指向头部（jack）
   System.out.println("====删除结点后遍历====");
   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 name){
   this.item = name;
}

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

LinkedList 的增删改查案例

package com.hspedu.list_;

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

@SuppressWarnings({"all"})
public class LinkedListCRUD {
    public static void main(String[] args) {
        //创建LinkedList
        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
            3. 执行 添加
            public boolean add(E e) {
                linkLast(e);
                return true;
            }
            4.将新的结点，加入到双向链表的最后
            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++;
            }
            */
            /*
            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 指向的双向链表的第一个结点拿掉
            private E unlinkFirst(Node<E> f) {
                // assert f == first && f != null;
                final E element = f.item;
                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;
            }
        */
    }
}

特殊点

remove有三种，可选择下标删除，可选择指定对象删除
第三种，没有参数，默认删除最后一个元素