通俗来说#xff0c;相比较于顺序表#xff08;物理上连续#xff0c;逻辑上也连续#xff09;#xff0c;链表物理上不一定连续。

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

通俗来说相比较于顺序表物理上连续逻辑上也连续链表物理上不一定连续。

1.单向或双向

在Java集合框架中的LinkedList底层实现的是无头双向循环链表。

LinkedList模拟实现

这里有一个问题为什么遍历的条件是curnull而不是cur.nextnull

我们可以知道此链表的尾结点next位置存的是null如果以cur.nextnull作为判断条件

那么当执行完循环中最后一条语句“cur

cur.next;”时此时由于尾结点的next为空所以会跳出循环相当于count少进行了一次计数那么最终的count值就是错误的。

public

{e.printStackTrace();}//在0位置插入调用头插法if(index

{addFirst(data);return;}//在尾位置插入调用尾插法if(index

size())

ListNode(data);//2、开始绑定节点node.next

cur;cur.prev.next

IndexNotLegalException(双向链表插入index位置不合法:

index);}}

LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节

点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。

LinkedList没有实现RandomAccess接口因此不支持随机访问。

LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O1

方法解释LinkedList()无参构造

java.util.ArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);//使用ArrayList构造LinkedListListString

list3