Java——LinkedList与链表介绍

链表（linked list） 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。

• 一、链表
• • 1、单(双)向链表
  • 2、(不)带头节点的链表
  • 3、(非)循环链表
  • 4. ArrayList和linkedList如何选择
• 二、linkedList
• • 1、使用
  • 2、常用方法
  • 3、遍历
• 三、模拟实现linkedList

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

单向链表

双向链表

不带头节点的链表

带头结点的链表

循环链表

非循环链表

在这些链表类型中，重点掌握的链表的类型有两种：

1. 无头单向非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
   
2. 无头双向链表： 在Java的集合框架库中linkedList底层实现就是无头双向循环链表。

ArrayList

• 频繁访问列表中的某一个元素。
• 只需要在列表末尾进行添加和删除元素操作。

注： ArrayList的缺点是不适合任意位置插入和删除。因为其在任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率较低。

linkedList

• 需要通过循环迭代来访问列表中的某些元素。
• 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

linkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

• linkedList 继承了 AbstractSequentialList 类。
• linkedList 实现了 List 接口，可进行列表的相关操作。
• linkedList 实现了 Deque 接口，可作为队列使用。
• linkedList 实现了 Cloneable 接口，可实现克隆。
• linkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

//无参构造
linkedList()
//使用其他集合容器中元素构造List
public linkedList(Collection c)

public static void main(String[] args) {
    //构造一个空的linkedList
    linkedList linkedList = new linkedList<>();
    linkedList.add("CSDN");
    linkedList.add("IDEA");
    linkedList.add("Java");
    
    //使用ArrayList构造linkedList
    List list = new java.util.ArrayList<>();
    List list2 = new linkedList<>(list);
}

 public static void main(String[] args) {
        //构造一个空的linkedList
        linkedList linkedList = new linkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList linkedList1 = new linkedList<>(linkedList);
        linkedList.add(5);
        linkedList.add(6);
        System.out.println("尾插入6个元素：");
        System.out.println("linkedList.size() = " + linkedList.size());
        System.out.println("linkedList = " + linkedList);
        System.out.println("将128插入位置3：");
        linkedList.add(3,128);
        System.out.println("linkedList = " + linkedList);
        System.out.println("将list1尾插入list：");
        linkedList.addAll(linkedList1);
        System.out.println("linkedList = " + linkedList);
        System.out.println("删除位置3的元素：");
        linkedList.remove(3);
        System.out.println("linkedList = " + linkedList);
        System.out.println("删除遇到的第一个3：");
        linkedList.remove((Object)3);
        System.out.println("linkedList = " + linkedList);
        System.out.println("linkedList.get(4) = " + linkedList.get(4));
        System.out.println("linkedList.set(5,128) = " + linkedList.set(5,128));
        System.out.println("before clear = " + linkedList1);
        linkedList1.clear();
        System.out.println("after clear = " + linkedList1);
        System.out.println("linkedList.contains(5) = " + linkedList.contains(5));
        System.out.println("linkedList.indexOf(6) = " + linkedList.indexOf(6));
        System.out.println("linkedList.lastIndexOf(5) = " + linkedList.lastIndexOf(5));
        System.out.println("linkedList = " + linkedList);
        System.out.println("linkedList.subList(2,7) = " + linkedList.subList(2, 7));
    }

    public static void main(String[] args) {
        linkedList linkedList = new linkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);
        linkedList.add(6);
        System.out.println("for-each遍历linkedList：");
        for (int i:linkedList) {
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println("迭代器遍历--正向遍历：");
        ListIterator it = linkedList.listIterator();
        while(it.hasNext())
            System.out.print(it.next()+" ");
        System.out.println();

        System.out.println("使用反向迭代器--反向迭代：");
        ListIterator rit = linkedList.listIterator(linkedList.size());
        while(rit.hasPrevious())
            System.out.print(rit.previous()+" ");
        System.out.println();
    }

之前有写过一篇博客专门实现Java——模拟实现linkedList