(69条消息) 详细介绍链表原理即应用(Java语言)

链表：LinkedList

首先我们要知道为什么要学习LinkedList，在学习链表之前肯定学过ArrayList，因为ArrayList存在缺陷，ArrayList的缺陷刚好是LinkedList的长处。

ArrayList和LinkedList有哪些区别呢？

1.存储方式

ArrayList底层使用数组来存储元素,是一块连续的内存,在物理逻辑上是连续的

LinkedList在物理逻辑上不一定是连续的,在逻辑上是连续的

2.增删查改进行区别

（1）当程序运用于增加,删除元素的场景比较多的时候,建议使用LinkedList.只需要修改指向就可以.而ArrayList需要大量元素位置的变化,时间复杂度为O(n).

（2）当程序运用于查找,修改场景比较多的时候,建议使用ArrayList.

LinkedList虽然也可以给下标,但也需要进行查找.时间复杂度为O(n),ArrayList可以通过下表直接确定到那个位置

注：顺序存储结构会预先分配内存，可能会造成存储空间浪费的问题（先定义一个数组，数组的空间分配大了的话，会造成内存浪费，链表就没有这个问题）

链表分为：

单链表、双链表、带头和不带头节点的链表、循环链表

//图中0x~~表示的是地址，随便写的，不是真正的地址，只是便于理解，也不是真正地址的格式，

//真正地址的格式大概是这样的：0x0012FFB0。

单链表

双链表

带头和不带头节点的单链表、双链表

 

循环单链表

 循环双链表

二、单链表的模拟实现

为了理解链表的运行机制，我们先自己实现一个链表（链表Java底层已经实现好了，可也直接用），作为初学者建议先自己实现单链表。

我实现的这个单链表有一下几个功能：

（1）打印链表 display 

 //打印单链表 public void display(){ ListNode cur = head; while(cur != null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }

（2）头插法插入元素addFirst（int data）

 //头插法 public void addFirst(int data){ ListNode node = new ListNode(data); if(this.head == null){ node.next = head; }else{ node.next = head; this.head = node; } }

（3）尾插法插入元素addLast（int data）

 //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if(head == null){ this.head = node; }else{ ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = node; } }

（4）任意位置插入元素addIndex（int index，int data）

 //任意位置插入，第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index size() || index 0){ System.out.println("添加的节点不合法"); } if(index == 0){ addFirst(data); return; } else if(index == size()){ addLast(data); return; } ListNode node = new ListNode(data); ListNode cur = Findcur(index); node.next = cur.next; cur.next = node; }//返回下标为index的节点 private ListNode Findcur (int index){ ListNode cur = this.head; while(index-1 != 0){ cur = cur.next; index--; } return cur; }

（5）查找是否包含关键字key是否在单链表当中contains（int key）

 //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = head; while(cur !=null) { if(cur.val == key){ return true; }else{ cur = cur.next; } } return false; }

（6）删除第一次出现关键字为key的节点remove（int key）

 //删除第一次出现关键字为key的节点 public void remove(int key){ if(key == head.val){ head = head.next; return; } ListNode cur = FindIndexCur(key); if(cur == null){ System.out.println("无该元素的节点"); }else{ ListNode chear = cur.next; cur.next = chear.next; } } //返回元素为key的节点 private ListNode FindIndexCur (int key){ ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ return cur; } cur = cur.next; } return cur.next; }

（7）删除所有值为key的节点removeAllKey(int key)

//删除所有值为key的节点 public void removeAllKey(int key){ if(this.head == null){ return; } ListNode cur = head.next; ListNode prev = head; while(cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if(head.val == key){ head = head.next; } }

（8）得到单链表的长度size（）

//得到单链表的长度 public int size(){ int count = 0; ListNode cur = head; while(cur != null){ count++; cur = cur.next; } return count; }

（9）清空链表clear（）

 //清空链表 public void clear(){ ListNode cur = head; ListNode curNode = null; while(cur != null){ curNode = cur.next; cur.next = null; cur = curNode; } head = null; }

以上代码的总合：

public class MySingleList { static class ListNode{//静态内部类 public int val;//数值域 public ListNode next;//存储下一个节点的地址//构造方法 public ListNode(int val){ this.val = val; } } public ListNode head;//代表链表的头接节点的引用 /** * 这里只是简单地进行链表的构造 */ public void createList(){ ListNode listNode1 = new ListNode(12); ListNode listNode2 = new ListNode(23); ListNode listNode3 = new ListNode(34); ListNode listNode4 = new ListNode(45); ListNode listNode5 = new ListNode(56); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; this.head = listNode1; } public void display(){ ListNode cur = head; while(cur != null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //头插法 public void addFirst(int data){ ListNode node = new ListNode(data); if(this.head == null){ node.next = head; }else{ node.next = head; this.head = node; } } //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if(head == null){ this.head = node; }else{ ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = node; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index size() || index 0){ System.out.println("添加的节点不合法"); } if(index == 0){ addFirst(data); return; } else if(index == size()){ addLast(data); return; } ListNode node = new ListNode(data); ListNode cur = Findcur(index); node.next = cur.next; cur.next = node; } private ListNode Findcur (int index){ ListNode cur = this.head; while(index-1 != 0){ cur = cur.next; index--; } return cur; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = head; while(cur !=null) { if(cur.val == key){ return true; }else{ cur = cur.next; } } return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ if(key == head.val){ head = head.next; return; } ListNode cur = FindIndexCur(key); if(cur == null){ System.out.println("无该元素的节点"); }else{ ListNode chear = cur.next; cur.next = chear.next; } } private ListNode FindIndexCur (int key){ ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ return cur; } cur = cur.next; } return cur.next; } //删除所有值为key的节点 public void removeAllKey(int key){ if(this.head == null){ return; } ListNode cur = head.next; ListNode prev = head; while(cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if(head.val == key){ head = head.next; } } //得到单链表的长度 public int size(){ int count = 0; ListNode cur = head; while(cur != null){ count++; cur = cur.next; } return count; } //清空链表 public void clear(){ ListNode cur = head; ListNode curNode = null; while(cur != null){ curNode = cur.next; cur.next = null; cur = curNode; } head = null; }}

在学习了单链表后，我们对链表也有了一定的认识，LinkedList的底层是一个双向链表，为了深入学习，深入理解，我们学习一下

三、双向链表的模拟实现

我要实现的双链表要有一下几个功能（这里模拟实现的是主要几个功能，LinkedList的功能众多）

（1）打印链表 display 

//打印链表 public void display(){ ListNode l1 = head; while(l1!=null){ System.out.println(l1.val); l1 = l1.next; } };

（2）头插法插入元素addFirst（int data）

 //头插法 public void addFirst(int data){ ListNode note = new ListNode(); if(head == null){ note.val = data; head = note; last = note; }else{ note.val = data; note.next = head; head.prev = note; head = note; } };

（3）尾插法插入元素addLast（int data）

 //尾插法 public void addLast(int data){ ListNode note = new ListNode(); if(head == null){ note.val = data; head = note; last = note; }else{ note.val = data; note.prev = last; last.next = note; last = note; } };

（4）任意位置插入元素addIndex（int index，int data）

 //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index==0){ addFirst(data); return; } if(index==size()){ addLast(data); return; } if(index 0 || index (size())){ System.out.println("下标错误"); return; } ListNode node = new ListNode(data); ListNode l1 = findList(index); node.next = l1; l1.prev.next = node; node.prev = l1.prev; l1.prev = node; }; //返回给定下标的节点 public ListNode findList(int index){ ListNode l1 = head; while(index!=0){ l1 = l1.next; index--; } return l1; }

（5）查找是否包含关键字key是否在单链表当中contains（int key）

 //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode l1 = head; while(l1!=null){ if(l1.val == key){ return true; } l1 = l1.next; } return false; };

（6）删除第一次出现关键字为key的节点remove（int key）

要注意是不是在第一个和最后一个，这两个需要特殊考虑

 //删除第一次出现关键字为key的节点 public void remove(int key){ //首先判断头节点是否为key if(head.val == key){ head = head.next; head.prev = null; return; } //要是没有值为key的节点,则退出 if(contains(key) == false){// System.out.println("无该关键字"); return; } ListNode l1 = head; int jishu = 1; while(l1.val!=key){ l1 = l1.next; jishu++; } if(jishu==size()){ l1.prev.next = null; return; } l1.prev.next=l1.next; l1.next.prev = l1.prev; };

（7）删除所有值为key的节点removeAllKey(int key)

 //删除所有值为key的节点 public void removeAllKey(int key){ ListNode l1 = head; while(l1!=null){ remove(key); l1 = l1.next; } };

（8）得到单链表的长度size（）

 //得到单链表的长度 public int size(){ ListNode node = head; int len = 1; while(node.next!=null){ len++; node = node.next; } return len; };

（9）清空链表clear（）

 public void clear(){ ListNode l1 = head.next; while(head!=null){ head.next=null; head.prev=null; head = l1; if(l1.next!=null){ l1 = l1.next; } } head = null; last = null; };

以上代码总合

/** * @Autor DYT * @Date 2022/11/22 */// 1、无头单向非循环链表实现public class DoubleLinkedList { static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode() { } public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; //头插法 public void addFirst(int data){ ListNode note = new ListNode(); if(head == null){ note.val = data; head = note; last = note; }else{ note.val = data; note.next = head; head.prev = note; head = note; } }; //尾插法 public void addLast(int data){ ListNode note = new ListNode(); if(head == null){ note.val = data; head = note; last = note; }else{ note.val = data; note.prev = last; last.next = note; last = note; } }; //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index==0){ addFirst(data); return; } if(index==size()){ addLast(data); return; } if(index 0 || index (size())){ System.out.println("下标错误"); return; } ListNode node = new ListNode(data); ListNode l1 = findList(index); node.next = l1; l1.prev.next = node; node.prev = l1.prev; l1.prev = node; }; //返回给定下标的节点 public ListNode findList(int index){ ListNode l1 = head; while(index!=0){ l1 = l1.next; index--; } return l1; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode l1 = head; while(l1!=null){ if(l1.val == key){ return true; } l1 = l1.next; } return false; }; //删除第一次出现关键字为key的节点 public void remove(int key){ //首先判断头节点是否为key if(head.val == key){ head = head.next; head.prev = null; return; } //要是没有值为key的节点,则退出 if(contains(key) == false){// System.out.println("无该关键字"); return; } ListNode l1 = head; int jishu = 1; while(l1.val!=key){ l1 = l1.next; jishu++; } if(jishu==size()){ l1.prev.next = null; return; } l1.prev.next=l1.next; l1.next.prev = l1.prev; }; //删除所有值为key的节点 public void removeAllKey(int key){ ListNode l1 = head; while(l1!=null){ remove(key); l1 = l1.next; } }; //得到单链表的长度 public int size(){ ListNode node = head; int len = 1; while(node.next!=null){ len++; node = node.next; } return len; };//打印链表 public void display(){ ListNode l1 = head; while(l1!=null){ System.out.println(l1.val); l1 = l1.next; } }; //清空链表 public void clear(){ ListNode l1 = head.next; while(head!=null){ head.next=null; head.prev=null; head = l1; if(l1.next!=null){ l1 = l1.next; } } head = null; last = null; };}

以上是想让我们深入理解链表的工作原理，在我们平时使用链表的时候是不需要写这么多代码的，Java底层已经帮我们写好了，我们直接调用就可以了，那么LinkedList有哪些方法可以直接调用呢？LinkedList怎么使用？LinkedList有多香？？？

四、LinkedList的使用 1、LinkedList的构造

（1）构造一个存放int类型数据的链表

 LinkedList Integer  linkedList = new LinkedList ();

（2）构造一个存放char类型数据的链表

 LinkedList Character integerList2 = new LinkedList ();

其他类型同理

注：list是线性表，linkedlist是链表，arraylist是顺序表，list是linkedlist和arraylist的父接口

写成：

 List Integer  linkedList = new LinkedList ();

也没有问题，只是linkedlist里边有的方法，可能list就没有，常见的都是有的。

2、LinkedList其他方法介绍（将以int类型 举例子）

LinkedList Integer integerList2 = new LinkedList ();

（1）尾插

integerList2.add(1);

（2）插入到给定下标

integerList2.add(3,4);//将4插入到3下标

（3）尾插链表c中的所有元素（c不受有影响）

 LinkedList Integer integerList3 = new LinkedList (); integerList3.add(111); integerList3.add(222); integerList3.add(333); integerList2.addAll(integerList3);

这样integerList2就在原来的基础上，尾插了integerList3的所有元素

（4）删除给定下标的元素

integerList2.add(3,4);//将4插入到3下标

（5）获取给定下标的元素

int a = integerList2.get(0);//a的值是链表integerList2的0下标的元素

（6）将给定下标的元素改成给定的元素

integerList2.set(2,888);//将下标为2的元素改成888。

（7）清空链表

void clear();

（8）判断给定元素是否在链表中

boolean panduan = integerList2.contains(2)；//判断元素2是否在链表中。

（9）返回第一个给定元素的下标

 System.out.println(integerList2.indexOf(222));

输出integerList2中第一个222的下标，如果没有，则输出-1。

（10）返回最后一个给定元素的下标

 System.out.println(integerList2.lastindexOf(222));

输出integerList2中最后一个222的下标，如果没有，则输出-1。

（11）删除第一次出现的给定的元素

integerList2.remove((Integer)222);

注：这个地方容易和删除给定下标的元素混淆，所删除的元素必须强制类型转化，否则电脑也无法识别要删除的是下标还是元素，Character也是。

（12）截取一个链表的部分元素给另一个链表

List Character integerList2 = new LinkedList (); integerList2 = integerList1.subList(0,4);

将链表integerList1中的0-4下标的元素给链表integerList2.

注：这个地方新的表必须是线性表而不是链表，integerList2必须是用List定义的

（13）打印链表

 LinkedList Integer linkedList = new LinkedList (); linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); linkedList.add(5); linkedList.add(6);

法1：直接打印

 System.out.println(linkedList);

打印效果：

 法2：for循环打印

 for (int x:linkedList) { System.out.println(x); }

打印效果：

法3：使用迭代器iterator

 Iterator Integer it = linkedList.iterator(); while (it.hasNext()){ //it.next()不仅会打印下一个,还会让it往后走一步 System.out.print(it.next()+" "); }

打印效果：

 法4：与法3同理

 ListIterator Integer listIterator1 = linkedList.listIterator(); while(listIterator1.hasNext()){ System.out.print(listIterator1.next()+" "); } System.out.println();

（14）倒序打印

法1：利用迭代器进行倒序打印

 System.out.println("倒序打印"); ListIterator Integer listIterator2 = linkedList.listIterator(linkedList.size()); //要给他size，要不然他找不到最后一个节点 while(listIterator2.hasPrevious()){ System.out.print(listIterator2.previous()+" "); } System.out.println();

法2：利用递归进行打印

 //利用递归打印链表 public void display2(ListNode head){ if(head == null){ return; } if(head.next == null){ System.out.println(head.val); return; } display2(head.next); System.out.println(head.val); }

本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。