🍀什么是LinkedList
LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
🌴LinkedList的模拟实现
我们在这里创建一个MyLinkedList的java文件用于模拟实现我们的LinkedList。
🚩创建双链表
我们要模拟实现LinkendList，首先我们要有我们的双链表，这里我们来实现一个双链表
双链表所需要元素
- 前驱节点：用于存储前一节点的位置，用prev表示
- 后继节点：用于储存下一节点的位置，用next表示
- 所需要储存的数据，用val表示
- 头节点：用head表示
- 尾节点：用last表示
如下图所示：
代码实现如下：
static class ListNode { public int val; public ListNode prev;//前驱 public ListNode next;//后继 public ListNode(int val) { this.val = val; } } public ListNode head;//头节点 public ListNode last;//尾节点
接下来我们将实现它的一些的功能
🚩头插法
实现思路：
- 首先判断头节点是否为null
- 若为null，则该节点就是头节点，也是尾节点
- 则将原先head的前驱节点指向位置改为新增节点位置
- 新增节点后驱节点指向位置改为head节点的位置
- 将新增节点设为新的头节点
代码实现如下：
//插法 O(1) public void addFirst(int data){ ListNode node = new ListNode(data); if(head == null) { head = node; last = node; }else { node.next = head; head.prev = node; head = node; } }
🚩尾插法
实现思路与头插法类似：
- 首先判断头节点是否为null
- 若为null，则该节点就是尾节点，也是头节点
- 将last的后继节点设为node
- node的前驱节点设为last
- node设为新的尾节点
代码实现如下：
//尾插法 O(1) public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { head = node; last = node; }else { last.next = node; node.prev = last; last = node; } }
🚩任意位置插入
首先我们需要对插入数据进行判断其合法线性
这里我们自定义一个异常，为ListIndexOutOfException
public class ListIndexOutOfException extends RuntimeException{ public ListIndexOutOfException() { } public ListIndexOutOfException(String message) { super(message); } }
其次我们可以对插入数据进行判断，若是在头尾进行插入，则可以直接用头插法与尾插法进行搞定
当所插入数据在中间时，我们首先要找到需要插入的节点，并返回，用cur接收
private ListNode findIndex(int index) { ListNode cur = head; while (index != 0) { cur = cur.next; index--; } return cur; }
当我们找到要插入的节点后，我们的步骤为以下几步
- 我们先将node的next置为cur；
- 让cur前驱节点所指向的节点的后继节点指向node
- 再将cur的前驱节点给node的前驱节点
- 最后将cur的前驱节点置为node；
代码实现如下：
//任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index < 0 || index > size()) { throw new ListIndexOutOfException("违规数据"); } if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } ListNode cur = findIndex(index); // ListNode node = new ListNode(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; }
🚩查找关键字
直接遍历查找即可
代码实现如下
//查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = head; while (cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; }
🚩链表长度
用一个len变量进行记录，遍历链表，最后进行返回即可
代码实现如下：
public int size(){ int len = 0; ListNode cur = head; while (cur != null) { len++; cur = cur.next; } return len; }
🚩打印链表
遍历链表进行输出即可
代码实现如下：
public void display(){ ListNode cur = head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
🚩删除第一次出现关键字为key的节点
我们大致的做法就是对链表进行遍历，遍历到相应的元素，删除即可，然后返回即可；
细分可分为三种情况
- 删除的是头节点
- 删除的是中间节点
- 删除的是尾节点
📌删除的是头节点
我们只需要将head向前走一步就好
这时候又分为只一个节点和有多个节点的情况
当只有一个节点时，我们的head只需要向前走一步就好
如果有多个节点，我们还需要将新节点的前驱节点置为null；
代码实现如下：
head = head.next; //只有一个节点 if(head != null) { head.prev = null; }
📌删除的是中间节点
我们分为两步：
- 将cur的前驱节点的后继节点变为cur的后继节点
- 将cur的后继节点的前驱节点变为cur的前驱节点
代码实现如下：
cur.prev.next = cur.next; cur.next.prev = cur.prev;
📌删除节点为尾节点
其实我们也分为两步：
- 将cur的前驱节点的后继节点变为cur的后继节点
- 将cur的前驱节点设为新的尾节点
我们发现其实前面一步和删除中间节点一样，所以这里我们将他们组合起来，在删除中间节点里面加入判断即可
代码实现如下：
//中间 尾巴 cur.prev.next = cur.next; //不是尾巴节点 if(cur.next != null) { cur.next.prev = cur.prev; }else { //是尾巴节点 last = last.prev; }
删除完后直接返回就好，如此一来，我们删除第一次出现关键字为key的节点完整代码也就可以出来了
代码如下：
//删除第一次出现关键字为key的节点 public void remove(int key){ ListNode cur = head; while (cur != null) { //开始删除了 if(cur.val == key) { //1. 删除的是头节点 if(cur == head) { head = head.next; //只有一个节点 if(head != null) { head.prev = null; } }else { //中间 尾巴 cur.prev.next = cur.next; //不是尾巴节点 if(cur.next != null) { cur.next.prev = cur.prev; }else { //是尾巴节点 last = last.prev; } } return; } cur = cur.next; } }
🚩删除所有值为key的节点
这个代码实现起来与删除第一次出现关键字为key的节点几乎是一模一样的；
我们只需要return删掉就好
代码实现如下：
//删除所有值为key的节点 public void removeAllKey(int key){ ListNode cur = head; while (cur != null) { //开始删除了 if(cur.val == key) { //1. 删除的是头节点 if(cur == head) { head = head.next; //只有一个节点 if(head != null) { head.prev = null; } }else { //中间 尾巴 cur.prev.next = cur.next; //不是尾巴节点 if(cur.next != null) { cur.next.prev = cur.prev; }else { //是尾巴节点 last = last.prev; } } } cur = cur.next; } }
🚩清空链表
我们只需要遍历整个链表，将每个节点的前驱与后继节点都置为null就好
代码实现如下：
public void clear(){ ListNode cur = head; while(cur != null) { cur.prev = null; cur = cur.next; cur.prev.next = null; } head = null; last = null; }
🚩完整代码实现
public class MyLinkedList { static class ListNode { public int val; public ListNode prev;//前驱 public ListNode next;//后继 public ListNode(int val) { this.val = val; } } public ListNode head;//头节点 public ListNode last;//尾节点 //头插法 O(1) public void addFirst(int data){ ListNode node = new ListNode(data); if(head == null) { head = node; last = node; }else { node.next = head; head.prev = node; head = node; } } //尾插法 O(1) public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { head = node; last = node; }else { last.next = node; node.prev = last; last = node; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index < 0 || index > size()) { throw new ListIndexOutOfException("违规数据"); } if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } ListNode cur = findIndex(index); // ListNode node = new ListNode(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; } private ListNode findIndex(int index) { ListNode cur = head; while (index != 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; } cur = cur.next; } return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ ListNode cur = head; while (cur != null) { //开始删除了 if(cur.val == key) { //1. 删除的是头节点 if(cur == head) { head = head.next; //只有一个节点 if(head != null) { head.prev = null; } }else { //中间 尾巴 cur.prev.next = cur.next; //不是尾巴节点 if(cur.next != null) { cur.next.prev = cur.prev; }else { //是尾巴节点 last = last.prev; } } return; } cur = cur.next; } } //删除所有值为key的节点 public void removeAllKey(int key){ ListNode cur = head; while (cur != null) { //开始删除了 if(cur.val == key) { //1. 删除的是头节点 if(cur == head) { head = head.next; //只有一个节点 if(head != null) { head.prev = null; } }else { //中间 尾巴 cur.prev.next = cur.next; //不是尾巴节点 if(cur.next != null) { cur.next.prev = cur.prev; }else { //是尾巴节点 last = last.prev; } } } cur = cur.next; } } public int size(){ int len = 0; ListNode cur = head; while (cur != null) { len++; cur = cur.next; } return len; } public void display(){ ListNode cur = head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } public void clear(){ ListNode cur = head; while(cur != null) { cur.prev = null; cur = cur.next; cur.prev.next = null; } head = null; last = null; } }
🎍LinkedList的使用
在集合框架中，LinkedList也实现了List接口，具体如下：
【说明】
- LinkedList实现了List接口
- LinkedList的底层使用了双向链表
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
- LinkedList比较适合任意位置插入的场景
🚩LinkedList的构造
构造代码如下：
import java.util.LinkedList; import java.util.List; public class Main { 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的其他常用方法介绍
方法使用代码如下：
import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); // add(elem): 表示尾插 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); // 在起始位置插入0 list.add(0, 0); // add(index, elem): 在index位置插入元素elem System.out.println(list); list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst() list.removeFirst(); // removeFirst(): 删除第一个元素 list.removeLast(); // removeLast(): 删除最后元素 list.remove(1); // remove(index): 删除index位置的元素 System.out.println(list); // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false if(!list.contains(1)){ list.add(0, 1); }list.add(1); System.out.println(list); System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置 System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置 int elem = list.get(0); // get(index): 获取指定位置元素 list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem System.out.println(list); // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回 List<Integer> copy = list.subList(0, 3); System.out.println(list); System.out.println(copy); list.clear(); // 将list中元素清空 System.out.println(list.size()); } }
🚩LinkedList的遍历
public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); // add(elem): 表示尾插 list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); System.out.println(list.size()); // foreach遍历 for (int e:list) { System.out.print(e + " "); } System.out.println(); // 使用迭代器遍历---正向遍历 ListIterator<Integer> it = list.listIterator(); while(it.hasNext()){ System.out.print(it.next()+ " "); } System.out.println(); // 使用反向迭代器---反向遍历 ListIterator<Integer> rit = list.listIterator(list.size()); while (rit.hasPrevious()){ System.out.print(rit.previous() +" "); } System.out.println(); }
🎄ArrayList和LinkedList的区别
⭕总结
关于《【数据结构】 LinkedList的模拟实现与使用》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！
