List集合之LinkedList（三）LinkedList总结

妖狐艹你老母 2023-10-04 09:38 29阅读 0赞

# 思维导图 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70][]

# 代码练习 #

import java.util.*;
    
    public class LinkedListTest {
        static Collection c = new ArrayList();
    
        static {
            Collections.addAll(c,"A","B","C","D");
        }
    
        public static void main(String[] args) {
    //        testFeatures();
    //        testConstructor();
    //        testMethodFromList();
    //        testMethodFromObject();
    //        testMethodFromDeque();
    //        testIterator();
    //        testListIterator();
    //        testDescendingIterator();
        }
    
        public static void testFeatures(){
            LinkedList linkedList = new LinkedList();
            linkedList.add(1);
            linkedList.add("123");
            linkedList.add("123");
            Person person = new Person("qfc", 18);
            linkedList.add(person);
            linkedList.add(person);
    
            System.out.println(linkedList);//[1, 123, 123, Person{name='qfc', age=18}, Person{name='qfc', age=18}]
            System.out.println(linkedList.get(3));//Person{name='qfc', age=18}
            /**
             * 特性测试结果：
             * 1.集合元素类型可以不一致，但是必须是引用类型
             * 2.集合容量是动态的
             * 3.LinkedList集合元素有索引，有序，可重复
             */
        }
    
        public static void testConstructor(){
            LinkedList linkedList = new LinkedList(c);
            System.out.println(linkedList);
    
            LinkedList linkedList1 = new LinkedList();
            System.out.println(linkedList1);
    
            /**
             * 构造器测试结果：
             * 无参构造器创建的是一个空集合
             * 带参构造器创建的是一个将参数c集合元素，按照c.toArray()后数组元素的顺序一一加入到LinkedList集合中。
             *
             * 无参构造器创建的集合对象的first,last节点都为null，size=0;
             * 有参构造器创建的集合对象的first,last取决于c集合的首元素和尾元素,size取决去c集合的元素个数。
             */
        }
    
        public static void testMethodFromList(){
            LinkedList linkedList = new LinkedList();
            // add(E e)
            // 该方法是将e元素插入到LinkedList尾部
            // 内部实现：
            // 0.记录last节点 即 Node copyOldLast = last;
            // 1.创建新节点  即Node newNode = new Node(copyOldLast,e,null)
            // 2.变更last指向  即 last = newNode
            // 3.判断copyOldLast是否为null，
            // 若copyOldLast为null，则说明原链表是空链，则newNode是唯一节点，即first也要指向newNode
            // 若copyOldLastb不为null，则说明原链表不是空链，则copyOldLast.next指向需要从null改为指向newNode
            // 5.size++  即集合元素个数加1
            // 6.modCount++ 即 集合结构化修改次数加1
            linkedList.add(0);
            linkedList.add(1);
            linkedList.add(2);
            linkedList.add(3);
            linkedList.add(4);
    
            // get(int index)
            // 该方法用于获取集合index索引处的节点的元素
            // 内部实现：
            // 1.由于LinkedList底层数据结构链表节点没有索引，但是节点是由顺序的，且是双向顺序
            // 所以LinkedList内部将头节点视为索引0，尾节点视为索引size-1,中间按顺序一次索引加1
            // 2.内部如何查找索引位置，由于链表维护上一步中的索引，所以无法实现随机访问，必须顺序访问实时计算链表节点的索引
            // 即每次获取某索引的节点，都要从first节点开始重新计算索引（+1），或者last节点考试重新计算索引（-1）
            // 3.如何实现计算链表节点索引
            // 我们知道 first的索引是0，first的下一个节点的索引是1，first的下下个节点的索引是2,...,last的所有是size-1
            // 用for循环遍历的话， 即
            // 由于最终要获得某索引的节点的item,所以遍历得到节点即可。且初始条件中 节点是first
            // 即 Node node = first
            // for(int i=0;i<index;i++) node = node.next;
            // 另外为了提升效率，采用了二分法查询，即 index<size/2时，采用Node node = first
            // index>=size/2时，采用Node node = last,且 for(int i=size;i>index;i--) node = node.prev
            linkedList.get(2);
    
            // add(int index,E e)
            // 该方法是将e插入到LinkedList集合的index索引处
            // 内部实现：
            // 1.判断插入索引index是否合法，即只能插入到底层链表的头（索引0），尾部（索引size）,中间（0~size-1）
            //    即 0 <= index <= size
            // 否则抛出索引越界异常，如下
    //        linkedList.add(6,5);//java.lang.IndexOutOfBoundsException: Index: 6, Size: 5
            // 2.当索引index合法时，将index位置的节点取出来备份
            // 即  Node copyIndexNode = node(index); 关于node(int index)方法会在就是get方法的逻辑
            // 3.创建新节点
            // 3.1.如果index=0，那么copyIndexNode就是头节点，则newNode插入后，newNode就是头节点。即first=newNode;newNode.prev=null,newNode.next=copyIndexNode
            // 3.2.如果index=size,那copyIndexNode就是null，则newNode插入后，newNode就是尾节点，即last=newNode,newNode.prev=copyIndexNode,newNode.next=null
            // 3.3.如果0<index<size,那么 newNode = new Node(copyIndexNode.prev,e,copyIndexNode);
            // 4. size++
            // 5. modCount++
            linkedList.add(5,5);
    
            // add(Collection c)
            // 该方法是将c集合中元素按迭代器迭代顺序（但不一定使用迭代器迭代）插入到LinkedList集合尾部
            // 1.将c集合转为数组 即 Object[] arr = c.toArray()
            // 2.判断c集合是否为空集合，即arr.length==0?返回false:继续下一步
            // 3.遍历arr数组元素
            // 3.1 创建遍历元素的节点，即 Node newNode0 = new Node(last,arr[0],null)
            // 3.2 创建遍历元素的节点，即 Node newNode1 = new Node(newNode0,arr[1],null),且newNode0.next=newNode1
            // 3.3按照3.2的逻辑重复操作到arr元素遍历完
            // 4. size+=arr.length 即集合元素个数增加了c集合元素个数个
            // 5. modCount++  即集合结构化修改次数+1
            linkedList.addAll(c);
    
            // add(int index,Collection c)
            // 该方法时将c集合中元素按迭代器迭代顺序（但不一定使用迭代器迭代）插入到LinkedList集合的index位置
            // 该方法的实现逻辑就是 add(int index,E e)和add(Collection c)两个方法结合
            linkedList.addAll(1,c);
    
            //System.out.println(linkedList);//[0, A, B, C, D, 1, 2, 3, 4, 5, A, B, C, D]
    
            // remove()
            // 该方法就是删除LinkedList集合头元素。
            // 内部实现：
            // 1.判断链表是否为空链表，若为空链表则抛出无此元素异常
    //        new LinkedList().remove();//java.util.NoSuchElementException
            // 2.若底层链表不是空链表，则删除该链表的头节点
            // 2.1 如果该链表只有一个节点，则这个唯一节点既是头节点，也是尾节点
            // 即删除了该节点，链表就为空链表，即first=null,last=null
            // 2.2 如果底层链表有多个节点，则
            // 2.2.1 备份头节点：Node copyFirNode = first;
            // 2.2.2 由于要删除头节点，所以头节点后一个节点就是新的头节点，即first = copyFirNode.next; first.prev = null;
            // 2.2.3 断开copyFirNode和新的first节点的联系，即copyFirNode.next = null
            // 2.2.4 彻底删除copyFirNode，此时copyFirNode的prev,next都是null，所以只要将copyFirNode.item=null，该元素就是真正的垃圾了
            // 3. size--
            // 4. modCount++
            linkedList.remove();
    
            // remove(int index)
            // 该方法表示删除指定索引处的集合元素
            // 内部实现
            // 1.判断index是否合法，即 0<=index<=size-1，因为集合元素的索引只在0~size-1
            // 2.获取index位置的节点，并备份该节点。即 Node copyIndexNode = node(index);
            // 3.获取该节点的前后节点并保存：Node BeforeIndexNode = copyIndexNode.prev; Node AfterIndexNode = copyIndexNode.next;
            // 4.删除index索引处的节点：即 copyIndexNode.prev=null,copyIndexNode.next=null,copyIndexNode.item=null
            // 5.建立BeforeIndexNode，AfterIndexNode之间的联系
            // 5.1 如果BeforeIndexNode==null,AfterIndexNode!=null,
            // 则说明被删除的copyIndexNode是头节点，则AfterIndexNode现在是新的头节点，即first=AfterIndexNode,AfterIndexNode.prev=null
            // 5.2 如果BeforeIndexNode！=null,AfterIndexNode==null
            // 则说明被删除的copyIndexNode是尾节点，则BeforeIndexNode现在是新的尾节点，即last=BeforeIndexNode,BeforeIndexNode.next=null
            // 5.3 如果BeforeIndexNode==null,AfterIndexNode==null,
            // 则说明被删除的copyIndexNode是唯一节点，即现在是空链表，即first=null,last=null
            // 5.4 如果BeforeIndexNode!=null,AfterIndexNode!=null,
            // 则需要 BeforeIndexNode.next = AfterIndexNode ; AfterIndexNode.prev = BeforeIndexNode
            linkedList.remove(4);
    
            // remove(Object o)
            // 该方法用于删除和o相同的第一个集合元素
            // 当o==null时，o无法使用equals，所以删除集合中第一个节点的item为null的节点
            // 当o!=null时，o使用equals去比较集合元素，删除第一个结果为true的元素所在节点
            linkedList.remove("A");
    
            // clear()方法用于清空集合元素
            // 内部实现：
            // 1.遍历循环链表节点，将每个节点的prev,item,next设置为null
            // 2.将first,last设置为null
            // 3.将size=0
            // 4.modCount++
            //linkedList.clear();
    
            // set(int index,E e)
            // 该方法用于将集合元素索引位置1的节点的item改为e
            // 内部实现，先判断index是否合法，即0<=index<size,再获取index处节点node(index)，并修改node(index).item=e
            linkedList.set(1,"F");
    
            // indexOf(Object o)用于获取o元素再集合中首次出现的位置索引
            // lastIndexOf(Object o)用于获取o元素在集合中末次出现的位置索引
            // 这两个方法本质也是遍历链表节点，找到和o相同的元素，只是indexOf是从首到尾遍历，lastIndexOf是从尾到首遍历
            // 比较时，o如果是null，采用==，o如果是非null，采用equals
            // 上述两个方法当找不到对应元素时返回-1
            linkedList.indexOf("B");
            linkedList.lastIndexOf("B");
    
            // contains(E e)用于判断集合中是否包含e
            // 内部实现：return indexOf(o) != -1
            linkedList.contains("B");
    
            // size()用于返回集合元素个数
            // 即 return size;
            linkedList.size();
    
            // toArray()用于将集合转为Object[]数组
            // 内部实现：
            // 1.先创建一个长度为size的Object[]数组
            // 2.遍历LinkedList底层链表的节点，并取出节点的item存入数组中
            linkedList.toArray();
    
            // toAarry(T[] a)用于将集合转成T[]数组
            // 当形参a数组的长度小于size时，创建一个T[]类型的长度为size的新数组
            // 当形参a数组的长度大于size时，则将大于size部分的索引元素设为null
            // 遍历链表，将集合元素存入数组0~size-1索引中。
            linkedList.toArray(new Object[0]);
        }
    
        public static void testMethodFromObject(){
            LinkedList linkedList = new LinkedList();
            Person p1 = new Person("qfc",18);
            Person p2 = new Person("zyx",19);
            Person p3 = new Person("swk",20);
            Person p4 = new Person("zbj",21);
    
            Collections.addAll(linkedList,p1,p2,p3,p4);
    
            System.out.println(linkedList.get(0));
    
            /**
             * 由于LinkedList实现了Cloneable接口，且重写clone方法，在clone方法中调用了super.clone()，获得对象拷贝
             * 后面将拷贝对象的first,last设为null,将size,modCount设为null
             * 然后遍历被拷贝对象的节点，将节点中的item取出，通过cloneObject.add(item);给克隆对象插入对应元素
             * 为什么不直接使用super.clone()结果呢？因为这样会导致 拷贝对象的first,last 和 被拷贝对象的first,last 指向同一个内存上节点，这实际上已经不算对象克隆了。
             */
            LinkedList clone = (LinkedList)linkedList.clone();
    
            Person person = (Person) clone.get(0);
            person.setName("sg");
            person.setAge(12);
    
            System.out.println(linkedList.get(0));
            /**
             * 说明：LinkedList的对象克隆是浅克隆
             */
        }
    
        public static void testMethodFromDeque(){
            LinkedList linkedList = new LinkedList(c);
            System.out.println(linkedList);
    
            //下面几个方法都是见名知意的
            linkedList.addFirst("A-");//[A-,A, B, C, D]
            linkedList.addLast("Z");//[A-,A, B, C, D, Z]
            linkedList.removeFirst();//[A, B, C, D, Z]
            linkedList.removeLast();//[A, B, C, D]
            linkedList.removeFirstOccurrence("A");//[B, C, D]
            linkedList.removeLastOccurrence("B");//[C, D]
    
            //下面几个方法是模拟顺序栈的操作
            linkedList.push("A-");//[A-,C, D]
            linkedList.peek();//[A-,C, D]
            linkedList.pop();//[C, D]
            System.out.println(linkedList);//[C, D]
    
            //下面几个方法是模拟双向栈的操作
            //注意offer()是栈底压栈
            linkedList.offer("A--");//[C, D, A--]
            linkedList.offerFirst("A-");//[A-, C, D, A--]
            linkedList.offerLast("Z");//[A-, C, D, A--, Z]
            linkedList.peekFirst();//[A-, C, D, A--, Z]
            linkedList.peekLast();//[A-, C, D, A--, Z]
            linkedList.poll();//[C, D, A--, Z]
            linkedList.pollFirst();//[D, A--, Z]
            linkedList.pollLast();//[D, A--]
            System.out.println(linkedList);
    
            //取出栈顶元素
            Object element = linkedList.element();//D
            System.out.println(element);
        }
    
        public static void testIterator(){
            LinkedList linkedList = new LinkedList(c);
            // iterator()本质是调用的LinkedList的listIterator(0);
            // 所以该方法本质是返回一个ListIterator对象
            Iterator iterator = linkedList.iterator();
            ListIterator listIterator = (ListIterator) iterator;
            boolean hasPrevious = listIterator.hasPrevious();
            System.out.println(hasPrevious);//由于该迭代器本质是listIterator(0),所以next为node(0),所以nextIndex=0,而hasPrevious内部是要求 nextIndex>0
            boolean hasNext = listIterator.hasNext();
            System.out.println(hasNext);//hasNext()本质就是要求 nextIndex<size
            listIterator.next();
            listIterator.next();
            listIterator.next();
            listIterator.next();
            System.out.println(listIterator.hasNext());
            System.out.println(listIterator.hasPrevious());
            listIterator.previous();
            listIterator.previous();
            listIterator.nextIndex();
            listIterator.previousIndex();
    
            /**
             * 到目前为止，以证明了LinkedList的iterator()方法，该方法虽然返回的是Iterator实现类对象，但实质是ListIterator实现类对象
             * 因为Iterator实现类对象没有previous(),hasPrevious()，nextIndex(),previousIndex()方法
             * 其他set,add方法就先不在此处演示
             */
        }
    
        public static void testListIterator(){
            /**
             * LinkedList有两种方式直接获取ListIterator实现类对象
             * 1.ListIterator listIterator();
             * 2.ListIterator listIterator(int index);
             * 其中1的内部实现就是调用了2的listIterator(0);这里不演示listIterator()
             */
    
            LinkedList linkedList = new LinkedList(c);
            ListIterator listIterator = linkedList.listIterator(4);
            while (listIterator.hasPrevious()){
                System.out.println(listIterator.previous());
            }
            System.out.println("====================================");
    
            System.out.println(listIterator.nextIndex());
            System.out.println(listIterator.previousIndex());
    
            System.out.println("====================================");
    
            while(listIterator.hasNext()){
                System.out.println(listIterator.next());
            }
    
            System.out.println("====================================");
    
            System.out.println(listIterator.nextIndex());
            System.out.println(listIterator.previousIndex());
    
            System.out.println("====================================");
    
            listIterator.add("E");
    
            System.out.println(linkedList);
    
            System.out.println("====================================");
    
            // 注意add操作后，lastReturned被重置为null,而remove操作时删除lastReturned索引上节点，所以该处remove操作会抛出非法状态异常
    //        listIterator.remove();//java.lang.IllegalStateException
    
            listIterator.previous();
            listIterator.remove();
            System.out.println(linkedList);
    
            System.out.println("====================================");
    
            // 注意remove操作后，lastReturned被重置为null,而set操作是修改lastReturned索引上的节点的item，所以该处set操作会抛出非法状态异常
    //        listIterator.set("DD");
    
            listIterator.previous();
            listIterator.set("DD");
            System.out.println(linkedList);
    
            System.out.println("====================================");
    
            listIterator.previous();
            listIterator.previous();
            // 注意foreachRemaining不是从头遍历集合，而是从nextIndex索引为止开始遍历剩下的集合元素
            listIterator.forEachRemaining(data-> System.out.println(data));
        }
    
        public static void testDescendingIterator(){
            LinkedList linkedList = new LinkedList(c);
            Iterator descendingIterator = linkedList.descendingIterator();
            while (descendingIterator.hasNext()){
                Object next = descendingIterator.next();
                System.out.println(next);
                if(next.equals("C")){
                    descendingIterator.remove();
                }
            }
            System.out.println(linkedList);
            System.out.println("====================================");
    
            LinkedList linkedList1 = new LinkedList(c);
            Iterator descendingIterator1 = linkedList1.descendingIterator();
    
            descendingIterator1.forEachRemaining(data-> System.out.println(data));
            /**
             * 测试DescendingIterator迭代器，发现它的hasNext,next,foreachRemaing都是逆序执行
             * 因为hasNext的内部实现调用的是ListItr的hasPrevious
             *    next的内部实现调用的是ListItr的previous
             *    foreachRemaining内部调用是自己的hasNext，和next
             */
        }
    }

package linkedlist;
    
    public class Person implements Cloneable{
        private String name;
        private int age;
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Person)) return false;
    
            Person person = (Person) o;
    
            if (getAge() != person.getAge()) return false;
            return getName() != null ? getName().equals(person.getName()) : person.getName() == null;
        }
    
        @Override
        public int hashCode() {
            int result = getName() != null ? getName().hashCode() : 0;
            result = 31 * result + getAge();
            return result;
        }
    
        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

# 思考题 #

## 为什么LinkedList不直接继承AbstractList，而要继承AbstractSequentialList？ ##

> 我们知道ArrayList,Vector直接继承了AbstractList。而LinkedList直接继承了AbstractSequentialList。
> 
> 而AbstractList，AbstractSequentialList作为List实现类的抽象父类，它们存在的意义是提取子类中重复代码形成模板。
> 
> 而ArrayList，Vector的底层是数组，LinkedList的底层是双向链表。它们实现基本操作如增删改查的的实现是不一样的。
> 
> 所以说 AbstractList是ArrayList，Vector的抽象，AbstractSequentialList是LinkedList的抽象。
> 
> 另外，AbstractSequentialList的基本操作都依赖于listIterator(int index)方法，而LinkedList中重写了listIterator(int index),所以AbstractSequentialList中的操作都依赖于LinkedList中的listIterator(int index)

## 为什么说ArrayList的容量是伪动态的？而说LinkedList的容量是真动态的？ ##

> 因为ArrayList的底层是数组。而数组的长度是固定的，一旦初始化，就无法再变更数组长度。
> 
> ArrayList的动态容量是 通过创建新数组来实现的。
> 
> 而LinkedList的底层是双向链表。而链表的长度不是固定，后期可以实时增加或减少。
> 
> 所以说LinkedList的容量 是 真动态的。

## 为什么说LinkedList的集合元素索引是伪索引？而ArrayList是真索引？ ##

> 因为ArrayList的底层是数组。而数组本身是有索引的。所以说ArrayList集合元素的索引是真索引。
> 
> 而LinkedList的底层是双向链表，而链表节点是没有索引能力的。体现在LinkedList元素上的索引，其实是底层链表的节点的顺序序号，即first节点的元素是索引0，last节点的元素是索引size-1。

## LinkedList的元素插入删除肯定比ArrayList快吗？ArrayList的查询操作一定比LinkedList的快吗？ ##

> 如果ArrayList容量足够的话，插入元素应该比LinkedList快。因为ArrayList可以随机访问，可以借助索引直接插入元素，不需要像LinkedList需要顺序访问，从first节点还是一个一个实时计算索引，然后创建新节点，删除旧节点，解开旧链接，创建新链接。
> 
> 还有ArrayList删除最后一个索引的元素 理论上是比 LinkedList删除元素快的，因为ArrayList删除最后一个索引的元素，只需要将底层数组该索引元素设置null即可。不需要移位操作。而LinkedList删除元素，实际上是删除节点，而删除节点前需要找到节点，这些动作比较耗时。
> 
> ArrayList的查询操作也是随机访问性的，即可以根据索引直接访问对应元素。
> 
> LinkedList查询首尾元素很快，因为first和last节点在二分法查询下都是第一个被遍历的节点。所以感觉也很快，不一定比ArrayList的慢。
> 
> 我们常说的LinkedList插入删除元素比ArrayList快，有如下场景
> 
> 1.ArrayList容量不足时，需要扩容，然后将老数组中元素全部按序复制到新数组中。
> 
> 2.ArrayList越靠前的索引处插入或删除元素时，后面元素都要做移位操作。
> 
> 而LinkedList由于是真动态容量，所以不需要手动扩容，另外LinkedList插入删除元素，底层链表不需要后面的节点移位，只需要在操作的地方解开链，再创建新链就可以了。
> 
> 我们常说的ArrayList查询元素比LinkedList快是，有如下场景
> 
> 1.LinkedList每次查询对应索引的元素，都要通过遍历链表节点，来实时计算每个节点元素的索引，如果是单次还好，如果是循环查索引，它的复杂度将是ArrayList的n倍。
> 
> 2.LinkedList采用二分法查询节点，并访问节点元素。如果是首尾节点还好，查询会很快。但是如果是靠近中间的节点，就会查询很慢。
> 
> 而ArrayList是可以根据索引直接访问对应元素的。
> 
> 所以只能本题的问题的前面加上一个前提词：大体上。
> 
> 大体上，ArrayList查询快，增删慢。大体上，LinkedList增删快，查询慢。

## 比较下Stack模拟栈和LinkedList模拟栈的区别 ##

> 二者的区别主要是底层数据结构上的。
> 
> Stack的底层是数组。LinkedList的底层是双向链表。
> 
> 数组和双向链表都可以模拟栈。栈数据结构的特点是：元素后进先出。主要操作有push,peek,pop
> 
> 而数组可以将每次push的元素存在数组的length-1索引位置，peek操作取出length-1索引位置的元素，pop是取出length-1索引位置的元素，并设置该索引元素为null（达到删除元素的目的）
> 
> 但是数组有个缺点就是容量固定，当push元素超出数组长度时，需要扩容，即创建新数组来转移存储。整体来说，性能不是很好。
> 
> 而双向链表模拟栈比数组更加合适，双向链表可以将first节点处当成栈顶，也可以将last节点当成栈顶，且双向链表push,pop操作起来就是创建新节点，新链接，删除老节点，老链接的事，没有扩容，转移存储这些麻烦的操作。peek就是获取栈顶的节点的元素。双向链表本身操作首尾节点就很快，所以说双向链表模拟栈太合适了。
> 
> 另外Stack只能模拟顺序栈，不能模拟双向栈。而LinkedList模拟双向栈简直就是蜜蜂掉到糖罐里，找到家了。相应的LinkedList的栈操作方法比Stack多，多的部分主要是双向栈的操作。
> 
> 如 offer(E e),offerLast(E e) 压栈（底）offerFirst(E e)压栈（顶）
> 
> poll(),pollFirst() 弹栈（顶） pollLast() 弹栈（底）
> 
> peek(),peekFirst() 获取栈顶元素 peekLast()获取栈底元素
> 
> push(E e) 压栈（顶）,pop() 弹栈（顶）

## 为什么说LinkedList是双向不循环链表呢？ ##

> JDK8中，LinkedList的first,last节点有特殊注释说明
> 
> 一般循环链表的first,last是链接的，即first.prev = last ; last.next = first;
> 
> 但是在JDK8 LinkedList源码中 关于 first,last节点的描述只有两种情况
> 
> 空链表:first = null, last = null
> 
> 非空链表 first.prev = null && first != null
> 
> last.next = null && last != null
> 
> 所以LinkedList从设计上来说，就不是循环链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70 1][]

## LinkedList支持对象克隆吗？是深克隆还是浅克隆？ ##

> LinkedList实现了Cloneable接口，且重写了clone()方法，重写的clone()中调用super.clone()。
> 
> 所以LinkedList要支持对象克隆。
> 
> 且还是浅克隆。因为clone()方法中没有对链表节点中item做对象克隆，而是直接使用了原对象节点中item的引用。

## 为什么说LinkedList是顺序访问集合，而ArrayList是随机访问集合？ ##

> 因为LInkedList的底层是双向链表，它访问链表节点中的元素，必须要从first遍历到对应节点的元素，才能访问，所以是顺序访问。
> 
> 而ArrayList的底层是数组，它访问数组元素可以借助数组索引，实现想访问哪就访问哪（注意不能越界），所以是随机访问。

## LinkedList有哪几种迭代器？分别有什么特点？ ##

> 从迭代器类型上来说有两种：1.Iterator迭代器 2.ListIterator迭代器
> 
> 但是这样分没有意义。
> 
> 因为获取这两种迭代器的方式各有两种：
> 
>  *  Iterator迭代器
> 
> 通过 iterator()方法获取
> 
> 通过 descendingListIterator()方法获取
> 
>  *  Listiterator迭代器
> 
> 通过 listIterator()方法获取
> 
> 通过 listIterator(int index)方法获取
> 
> 其中iterator(),listIterator()方法本质都是调用的listIterator(int index),所以可以重新分类
> 
>  *  ListItr实现类迭代器
> 
> 通过 iterator()方法获取
> 
> 通过 listIterator()方法获取
> 
> 通过 listIterator(int index)方法获取
> 
>  *  DescendingListIterator实现类迭代器
> 
> 通过 descendingListIterator()方法获取
> 
> 特点
> 
> ListItr实现类迭代器就是双向迭代器，可以顺序迭代，也可以逆序迭代，可以删除迭代元素，也可以增加迭代元素，也可以修改迭代元素，还可以遍历处理剩余迭代元素。
> 
> DescendingListIterator实现类迭代器是单向迭代器，且是逆序迭代，即它的hasNext(),next()，foreachRemaining(Consumer c)这些方法都是逆序迭代的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210330192254226.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210330212953264.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA=,size_16,color_FFFFFF,t_70