Java

LinkedList简介LinkedList的模拟实现LinkedList的使用LinkedList的构造LinkedList的方法LinkedList的遍历

上篇博客详细写了ArrayList的相关问题包括上图极其重要我会在最近几篇博客中都有附上。

ArrayList的优点很明显底层逻辑是一个数组它通过下标去访问数据的速度非常快。

但是在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低

所以java集合框架中引入了LinkedList类即链表结构。

链表MySingleList

之前C语言了解过这方面的知识C语言—链表专题所以我们有一定的基础我相信链表对于大家一定是熟悉的存在。

我们先由易入难先自己尝试一下单链表MySingleList的功能实现为接下来的

LinkedList(无头双向链表)

ListNode(data);node.nex***ad;headnode;}尾插法

Overridepublic

ListNode(data);if(headnull){head

curhead;while(cur.next!null){cur

cur.next;}cur.nextnode;}任意位置插入,第一个数据节点为0号下标

Overridepublic

lensize();if(index0||indexlen){System.out.println(index位置不合法);return;}if(index0){addFirst(data);return;}if(indexlen){addLast(data);return;}ListNode

curhead;while(index-1!0){curcur.next;index--;}ListNode

nodenew

cur.next;cur.nextnode;}查找是否包含关键字key是否在单链表当中

Overridepublic

curhead;while(cur!null){if(cur.valkey){return

Overridepublic

{if(headnull){return;}if(head.valkey){headhead.next;return;}ListNode

curfindNodeOfKey(key);if(curnull){return;}ListNode

del

cur.next;cur.nextdel.next;}private

ListNode

curhead.next;while(cur!null){if(cur.valkey){prev.nextcur.next;cur

cur.next;}if(head.valkey){headhead.next;return;}}}得到单链表的长度

Overridepublic

curhead;while(cur!null){len;curcur.next;}return

len;}清空链表

curhead;while(cur!null){ListNode

curNcur.next;cur.nextnull;curcurN;}headnull;}LinkedList简介

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

LinkedList实现了List接口LinkedList的底层使用了双向链表LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1)LinkedList比较适合任意位置插入的场景

头插法

ListNode(data);if(headnull){headlastnode;}else{node.nex***ad;head.prevnode;headnode;}}尾插法

Overridepublic

ListNode(data);if(headnull){headlastnode;}else{last.nextnode;node.prevlast;last

last.next;}}任意位置插入,第一个数据节点为0号下标

Overridepublic

lensize();if(index0||indexlen){return;}if(index0){addFirst(data);return;}if(indexlen){addLast(data);return;}ListNode

nodenew

ListNode(data);node.nextcur;cur.prev.nextnode;node.prevcur.prev;cur.nextnode;}

private

count0;while(cur!null){if(cur.valkey)

{return

curhead;while(cur!null){//开始删除if(cur.valkey){//有可能是头节点if(curhead){head

head.next;if(head!null){head.prevnull;}}else{cur.prev.next

cur.next;if(cur.nextnull){//有可能是尾节点last

Overridepublic

curhead;while(cur!null){//开始删除if(cur.valkey){//有可能是头节点if(curhead){head

head.next;if(head!null){head.prevnull;}}else{cur.prev.next

cur.next;if(cur.nextnull){//有可能是尾节点last

cur.prev;}}}else{cur

前面我们自主实现了LinkedList的各种方法只是为了大家更好的理解和学习以后做题可能会运用到类似的想法或思路可以更加高效的完成题目平时也可以直接使用LinkedList下的方法。

如下图

public

LinkedListInteger();LinkedListInteger

list2

LinkedListInteger();//使用ArrayList构造LinkedList

ListString

LinkedList(list3);}为什么可以有的构造可以用List有的用LinkedList,甚至出现了ArrayList一切都是这张贯穿整个数据结构的图。

public

表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);//

subList(from,

to)之间的元素构造一个新的LinkedList返回ListInteger

list2

System.out.println(list);System.out.println(list2);list.clear();

将list中元素清空System.out.println(list.size());

之前ArrayList博客【Java数据结构】—List(ArrayList)

public

表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());//

使用反向迭代器---反向遍历ListIteratorInteger

list.listIterator(list.size());while

(it.hasPrevious()){System.out.print(it.previous()

);}

不同ArrayListLinkedList存储空间物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(n)头插空间不够时扩容不存在容量的概念运用场景元素高效存储频繁访问频繁任意位置的插入和删除

如果这个系列博客对你有帮助的话可以点一个免费的赞并收藏起来哟~

我们下期不见不散~~Java