刷网站排名 优帮云,成都文创产品设计公司,怎样下载别人网站自己做的视频,安徽省建筑工程信息平台文章目录 #x1f340;什么是LinkedList#x1f334;LinkedList的模拟实现#x1f6a9;创建双链表#x1f6a9;头插法#x1f6a9;尾插法#x1f6a9;任意位置插入#x1f6a9;查找关键字#x1f6a9;链表长度#x1f6a9;打印链表#x1f6a9;删除第一次出现关键字为… 文章目录 什么是LinkedListLinkedList的模拟实现创建双链表头插法尾插法任意位置插入查找关键字链表长度打印链表删除第一次出现关键字为key的节点删除的是头节点删除的是中间节点删除节点为尾节点 删除所有值为key的节点清空链表完整代码实现 LinkedList的使用LinkedList的构造LinkedList的其他常用方法介绍LinkedList的遍历 ArrayList和LinkedList的区别⭕总结 什么是LinkedList
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的后继节点设为nodenode的前驱节点设为lastnode设为新的尾节点 代码实现如下 //尾插法 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) {
// 构造一个空的LinkedListListInteger list1 new LinkedList();ListString list2 new java.util.ArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);
// 使用ArrayList构造LinkedListListString list3 new LinkedList(list2);}
}LinkedList的其他常用方法介绍 方法使用代码如下
import java.util.LinkedList;
import java.util.List;public class Main {public static void main(String[] args) {LinkedListInteger 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);
// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.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否则返回falseif(!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位置的元素设置为elemSystem.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回ListInteger 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) {LinkedListInteger 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();
// 使用迭代器遍历---正向遍历ListIteratorInteger it list.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();
// 使用反向迭代器---反向遍历ListIteratorInteger rit list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() );}System.out.println();}ArrayList和LinkedList的区别 ⭕总结
关于《【数据结构】 LinkedList的模拟实现与使用》就讲解到这儿感谢大家的支持欢迎各位留言交流以及批评指正如果文章对您有帮助或者觉得作者写的还不错可以点一下关注点赞收藏支持一下
