【数据结构】LinkedList与链表

目录

链表

1、链表的概念及结构

 2、LinkedList的使用

2、1什么是LinkedList

2、2LinkedList的使用

3、LinkedList的遍历

4、LinkedList的模拟实现

 5、ArrayList和LinkedList的区别

上篇已经熟悉了ArrayList的使用，ArrayList底层使用数组来存储元素。由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。

因此，java集合中又引入了LinkedList，即链表结构。

链表

1、链表的概念及结构

链表大分类

1.  单向或者双向
2.  带头或者不带头
3.  循环或者非循环

2、LinkedList的使用

2、1 什么是LinkedList

LinkedList官方文档

在集合框架中，LinkedList也实现了List接口，具体如下：

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

2、2 LinkedList的使用

LinkedList 的构造

 public static void main ( String [] args ) {

     // 构造一个空的 LinkedList

     List < Integer > list1 = new LinkedList <> ();

     List < String > list2 = new java . util . ArrayList <> ();

     list2 . add ( "JavaSE" );

     list2 . add ( "JavaWeb" );

     list2 . add ( "JavaEE" );

     // 使用 ArrayList 构造 LinkedList

    List < String > list3 = new LinkedList <> ( list2 );

 }

LinkedList常用方法 

以上就是 LinkedList常用方法 ，需要多练熟悉用法

3、LinkedList的遍历

 LinkedList<Integer> list1=new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);

1、for循环遍历 

 for (int i = 0; i <list1.size() ; i++) {System.out.print(list1.get(i)+" ");}System.out.println(" ");

2、foreach遍历

  for (Integer i:list1){System.out.print(i+" ");}System.out.println(" ");

3、使用迭代器遍历---正向遍历

   ListIterator<Integer> it= list1.listIterator();while(it.hasNext())System.out.print(it.next()+" ");System.out.println(" ");

ListIterator<Integer> rit= list1.listIterator(4);while(rit.hasPrevious())System.out.print(rit.previous()+" ");System.out.println(" ");}

4、LinkedList的模拟实现

模拟实现 LinkedList链表。

public class MyLinkedList {static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null) {head = last = node;return;}node.next=head;head.prev=node;head=node;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null) {head = last = node;return;}last=head;while(last.next!=null){last=last.next;}last.next=node;node.prev=last;last=last.next;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){int len=size();if(index<0||index>len) {System.out.println("index位置不合法");return false;}if(index==0) {addFirst(data);return true;}if(index==len) {addLast(data);return true;}ListNode cur=findnode(index);ListNode node=new ListNode(data);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;return true;}private ListNode findnode(int index){ListNode cur=head;while(index!=0){index--;cur=cur.next;}return cur;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key)return true;cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){if(cur==head){head=head.next;if(head==null)return;}else {cur.prev.next=cur.next;if(cur.next==null){last=last.prev;}else{cur.next.prev=cur.prev;}}return;}cur=cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){if(cur==head){head=head.next;if(head!=null)head.prev=null;}else{cur.prev.next=cur.next;if(cur.next==null){last=last.prev;}else{cur.next.prev=cur.prev;}}}cur=cur.next;}}//得到单链表的长度public int size(){int count=0;ListNode cur=head;if(head==null)return 0;while(cur!=null){count++;cur=cur.next;}return count;}public void display(){ListNode cur=head;if(head==null)return;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println(" ");}public void clear(){ListNode cur=head,curN=head;while(cur!=null){curN=cur.next;cur.next=null;cur.prev=null;cur=curN;}head=last=null;}}

 5、ArrayList和LinkedList的区别

【数据结构】LinkedList与链表学习到这里