1.为什么要学习LinkedList我们刚刚学习了ArrayList增添数据需要扩容操作浪费空间。查找数据的时间复杂度按下标索引的可以O1按内容查找的就需要ON。添加某一点的数据需要把后面的数据后移时间复杂度为ON所以ArrayList适合给定下标的查找更新在任意位置插入删除数据方面适合使用LinkedList。2.LinkedList2.1链表的概念链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接。也就是说在链表中内存地址不一定连续但是逻辑上一定是连续的物理上不一定连续。注链表结构分为单向与双向循环与非循环带头和不带头组合方式很多我们主要学习带头单向不循环。2.2节点我们可以想象火车火车是由一节节车厢连接而成在链表中我们称这一节节车厢为节点。节点一共分为上下两个部分上半部分我们用来存放数据定义为val下半部分用来存放下一个节点的地址定义为next。如图所示我们知道12的内存地址是0X187定义第一个节点为head,当我们把curA.next cur,此时curA的next指针会指向curB的地址curB的next仍然是null代表后面没有节点了如下图所示2.3head在链表中head可以是头指针不是节点没有val,用来存储第一个节点的地址也可以是一个节点头节点他的val 可以是空的next指向下一个节点。2.4节点代码部分class ListNode{ int val; ListNode next; public ListNode(){} public ListNode(int val){ this.val val; } }3.链表的实现3.1ILinkedList首先我们先定义一个ILinkedList接口实现链表的方法public interface ILinkedList { //头插法 void addFirst(int data); //尾插法 void addLast(int data); //任意位置插⼊,第⼀个数据节点为0号下标 void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 boolean contains(int key); //删除第⼀次出现关键字为key的节点 void remove(int key); //删除所有值为key的节点 void removeAllKey(int key); //得到单链表的⻓度 int size(); void clear(); void display(); }3.2MySingleList用MySingleList实现ILinkedList接口。Override public void addFirst(int data) { } Override public void addLast(int data) { } Override public void addIndex(int index, int data) { } Override public boolean contains(int key) { return false; } Override public void remove(int key) { } Override public void removeAllKey(int key) { } Override public int size() { return 0; } Override public void clear() { } Override public void display() { }我们可以在MySIngleList类里面写一个静态内部类表示节点static class ListNode{ public int val; public ListNode next; public ListNode(){} public ListNode(int val){this.val val;} }接下来定义一个链表我们将在这个链表上实现插入删除等操作(1)public ListNode head;//头节点 public void createNode(){ ListNode node1 new ListNode(12); ListNode node2 new ListNode(23); ListNode node3 new ListNode(34); ListNode node4 new ListNode(45); }此时每个节点都是单独存在的head不指向任何节点我们需要把节点连在一起形成链表并且head指向头节点。2public void createNode(){ ListNode node1 new ListNode(12); ListNode node2 new ListNode(23); ListNode node3 new ListNode(34); ListNode node4 new ListNode(45); node1.next node2; node2.next node3; node3.next node4; head node1; }链表创建好了接下来我们一步步实现ILinkedList的功能。3.3display , size和clean1display打印链表我们只需要打印每个链表的val值定义一个临时指针cur用来遍历head不能用来遍历否则我们的头节点就丢了链表就找不到起点了在让cur cur.next保证cur null。public void display() { ListNode cur head; while(cur ! null){ System.out.print(cur.val ); cur cur.next; } System.out.println(); }(2)size定义一个int变量count用来表示链表节点总数同样定义一个临时指针用来遍历直至curnull返回count值。public int size() { int count 0; ListNode cur head; while(cur ! null){ count; cur cur.next; } return count; }3clean可以直接this.head null也可以定义一个临时指针cur指向head在while循环里cur null的条件下我们可以定义一个curN cur.next这样我们先让cur null我们需要cur原来的next这时候curN的作用就体现出来了指向cur.next的地址所以我们在清除了cur的地址后可以通过cur curN继续一个一个的清除cur的每一个节点。public void clear() { ListNode cur head; while(cur ! null){ ListNode curN cur.next; cur null; cur curN; } this.head null; }3.4addFirst如果想要将data节点插入链表的最前面需要将data的next指向链表的第一个节点值12地址是0X331我们可以定义一个节点cur值为data地址为空我们让cur.next head第一个节点变成了cur。head里存放的是第一个节点的地址所以此时head必须是指向这个插入的节点即head cur 。接下来我们写代码public void addFirst(int data) { ListNode cur new ListNode(data); cur.next head; head cur; }3.5addLast我们想将一个存放data数据的节点插到链表的最后一个首先需要判断链表是否为空空的话直接将head指向插入节点如果不为空我们需要遍历链表遍历到最后一个将链表最后一个节点的next指向0X399。定义一个临时指针cur遍历列表直到最后一个节点此时cur.next null,此时while循环判断条件为cur.next ! null否则执行cur.next curN的时候会抛出空指针异常。接下来是代码部分public void addLast(int data) { ListNode curN new ListNode(data); if(head null){ head curN; return; } ListNode cur head; while(cur.next ! null){ cur cur.next; } cur.next curN; }3.6addIndex我们想在index位置插入这个节点首先我们需要判断index位置是否合法可以自定义一个异常写一个判断位置合法的方法合法的话我们需要将链表index插入节点我们需要定义一个index前一个位置的临时指针cur将cur.next指向插入的节点定义为node指向之后原来index位置原来的指针以及index后面的位置都不见了所以我们需要定义一个临时指针curN存储index位置原来的节点。接下来我们来写代码//自定义一个检查Index位置异常 public class CheckIndexException extends RuntimeException{ public CheckIndexException(){} public CheckIndexException(String msg){ super(msg); } } //MYSingleList类里面 //检查Index合法性方法 public void checkIndex(int index){ if(index 0 || index size()){ throw new CheckIndexException(index位置不合法index); } } public void addIndex(int index, int data) { checkIndex(index); if(index 0){ addFirst(data); return ; } if(index size()){ addLast(data); return; } ListNode cur head; ListNode curN head.next; ListNode node new ListNode(data); int count 0; while(count ! index - 1){ cur cur.next; curN curN.next; count; } cur.next node; node.next curN; }其中按照Index查找可以单独写一个findIndex方法这样以后按照Index查找就不用每次写一个while循环了public void addIndex(int index, int data) { checkIndex(index); if(index 0){ addFirst(data); return ; } if(index size()){ addLast(data); return; } ListNode cur findIndex(index); ListNode node new ListNode(data); /*int count 0; while(count ! index - 1){ cur cur.next; curN curN.next; count; }*/ node.next cur.next; cur.next node; } public ListNode findIndex(int index){ ListNode cur head; int count 0; while(count ! index - 1){ cur cur.next; count; } return cur; }3.7contains这个就比较简单我们只需要遍历链表查看链表是否存在数据key首先检查head是否为空空的话直接返回布尔值false不为空就进入下一步遍历找到key直接返回true找不到返回falsepublic boolean contains(int key) { if(head null){ return false; } ListNode cur head; while(cur ! null){ if(cur.val key){ return true; } cur cur.next; } return false; }3.8remove和removeAllKey(1)remove如果head为空直接return不为空使用contains返回值是true的话证明key在链表里存在我们定义两个临时指针一个指向key节点的前一个节点cur一个指向key节点curN再将cur.next curN.next就可以删掉key节点其中找到key节点可以单独写一个findKey方法。接下来就是代码部分public void remove(int key) { if(head null){ return ; } if(head.val key){ head head.next; return; } if(contains(key)){ ListNode cur findKey(key); ListNode curN cur.next; cur.next curN.next; }else{ System.out.println(没有找到你要找的key值); return; } } public ListNode findKey(int key){ ListNode cur head; while(cur.next ! null){ if(cur.next.val key){ return cur; } cur cur.next; } return null; }2removeAllKey如果key 23我们需要把链表中val 23的节点全部删除首先我们需要判断head是否为空空的话直接return不空我们进入下一步我们需要两个临时指针一个cur指向key节点的前一个节点另一个curN则表示key节点这是我们定义curN cur.next;所以while循环条件是cur.next ! null,不然cur为空时curN cur.next会显示空指针异常。接下来我们进入while循环if语言判断curN.val 是否等于key,等于的话cur.next curN.next;curN curN.next;不等于的话cur curN;curN curN.next;最后跳出while循环判断head的val是否等于key因为我们循环里判断的是curN是head.next等于我们要head head.next不等于直接结束。public void removeAllKey(int key) { if(head null){ return; } ListNode cur head; ListNode curN cur.next; while(cur.next ! null){ if(curN.val key){ cur.next curN.next; curN curN.next; }else{ cur curN; curN curN.next; } } if(head.val key){ head head.next; } }