网站建设福建,杭州网站建设费用多少,中国建设网站用户名,软件工程项目开发的步骤文章目录一、模拟实现单链表成员属性成员方法0#xff0c;构造方法1#xff0c;addFirst——头插2#xff0c;addLast——尾插3#xff0c;addIndex——在任意位置插入3.1#xff0c;checkIndex——判断index合法性3.2#xff0c;findPrevIndex——找到index-1位置的结点…
文章目录一、模拟实现单链表成员属性成员方法0构造方法1addFirst——头插2addLast——尾插3addIndex——在任意位置插入3.1checkIndex——判断index合法性3.2findPrevIndex——找到index-1位置的结点4contains——判定是否包含某个元素5 remove——删除第一次出现关键字为key的结点5.1 findPrevKey——找到key结点的前一个结点6 removeAll——删除所有值为key的结点7size——获取单链表长度8clear——清空单链表9display——打印链表二、Java提供的LinkedList1LinkedList 的说明2使用LinkedList2.1LinkedList 实例化方式2.2LinkedList 常用方法链表和顺序表对比总结提示是正在努力进步的小菜鸟一只如有大佬发现文章欠佳之处欢迎评论区指点~ 废话不多说直接发车~
一、模拟实现单链表
认识链表 链表是一种物理存储结构上 非连续 存储结构数据元素的 逻辑顺序 是通过链表中的引用链接次序实现的 。
说人话链表就是 “链接” 起来的。可以理解为火车火车是由一节节车厢 “链接” 而成的而链表是由一个个结点/节点 “链接” 而成的
链表的结构可以细分为八种我们主要掌握两种即可 1无头单向非循环 结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
2无头双向循环 在Java的集合框架库中LinkedList底层实现就是无头双向循环链表 为什么要模拟实现 自己模拟实现 简易版的 顺序表的增删查改等主要功能大致理解顺序表的设计思想 再对比学习 Java 提供的集合类当中的 LinkedList在学习 Java 的 LinkedList 常用方法的同时也能学习源码的思想 我们模拟实现的是 无头单项非循环 链表
成员属性
Java 中的 LinkedList 是集合框架中的一个类要模拟实现链表也得自己实现一个类首先要考虑这个类中的成员属性
已经说过链表是由结点 “链接” 而成的那么需要定义一个 静态内部类 Node其中有两个域 值域 value 来记录这个结点的值 指针域 next来记录下一个结点的地址
还需要一个 成员变量head 来记录当前链表的头结点
为了方便测试全部设置为 public
public class MyLinkList {// 静态内部类不依赖于链表对象可以单独存在static class Node {public int value;public Node next;// Node类型的next值存放下一个节点的地址public Node(int value) {this.value value;}}public Node head;// 链表的头节点 ⚠️模拟实现重在理解理想为了简便不使用泛型数组中存放 int 类型 成员方法
// 无头单向非循环链表实现public class MyLinkList {// 1头插public void addFirst(int data){}// 2尾插public void addLast(int data){}// 3任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){}// 4查找是否包含关键字key是否在单链表当中public boolean contains(int key){}// 5删除第一次出现关键字为key的节点public void remove(int key){}// 6删除所有值为key的节点public void removeAllKey(int key){}// 7得到单链表的长度public int size(){}// 8清空链表public void clear() {}// 9打印官方没有这个方法写出来方便我们自己测试public void display() {}
}0构造方法
模拟的链表的这个类中构造方法只有内部类 Node 的构造方法只用来对结点的 value 域赋值即可指针域 next 不赋值默认为 null 在相应的方法内修改 Node 的指针域 next // 静态内部类不依赖于链表对象可以单独存在static class Node {public int value;public Node next;// Node类型的next值存放下一个节点的地址public Node(int value) {this.value value;}} 1addFirst——头插
❗️❗️和顺序表不同链表是由一个个结点组成的而顺序表可以理解为一个数组 顺序表插入之前必须考虑数组是否以及满了而链表只需要关心各个结点的next即可
我们还有一个成员属性head是用来记录头结点的 链表的头插操作就是 1new 一个结点 node类型是 Node 2链接把头结点的地址 head 的值赋给 node 的指针域 next 3head 记录新的头结点 public void addFirst(int value) {Node node new Node(value);node.next head;head node;}2addLast——尾插
尾插步骤 1new 一个 node类型是 Node 2找到尾结点 3链接把 node 的值也就是地址赋给尾结点的指针域 next
如何找到尾结点呢 需要 从头结点开始遍历链表找到一个结点的指针域 next 域为 null它就是尾结点 head 是用来标记头结点的所以 head 不能随意更改 我们需要再定义一个 Node 类型的 cur让 cur 遍历链表
当 cur 找到尾结点后需要让此时的尾结点和新结点 node 连接上 即 cur.next node;如图
cur 从头开始遍历链表 Node cur head;遍历链表的过程就是一个循环如果cur.next null 时跳出循环 如果不满足条件说明cur此时不是尾结点那么cur要往下走如何实现呢
cur 这个变量中存放的值 要更改为下一个结点的地址cur cur.next
写到这里就要小心了cur.next这一句代码是要访问 cur 的 next 域如果 cur null 时这里就会发生空指针异常
那么有没有可能会这种情况呢 cur 是从 head 开始往后遍历的那么如果 head 一开始就是 null 也就是链表为空时cur 就会被 head 赋值成 null就会发生空指针异常 所以当链表为空时就不需要遍历链表找尾结点直接把 node 的值赋给 head 即可 完整代码 public void addLast(int value) {Node node new Node(value);// 链表为空的情况if (head null) {head node;return;}Node cur head;// 找到最后一个结点的位置while (cur.next ! null) {cur cur.next;}cur.next node;}3addIndex——在任意位置插入
官方规定第一个数据的位置是0和数组的位置下标规则一致
第一个参数就是 index首先要判断 index 的合法性
3.1checkIndex——判断index合法性
index0 || index 链表长度是不合法的 public void checkIndex(int index) {if (index 0 || index size()) {// size()方法获取链表长度遍历链表即可比较简单不多赘述throw new LinkListIndexOutOfException(这个位置不合法);// 异常处理}}index 合法的情况下如何在index位置插入删除呢 index 0就是头插index 链表长度就是尾插主要是链表中间位置的插入和删除 要想在两个结点中间插入新结点首先要找到这两个结点的地址 找到index -1结点的位置也就相当于找到了index结点的位置
3.2findPrevIndex——找到index-1位置的结点 public Node findPrevIndex(int index) {Node cur head;int count 0;while (count ! index - 1) {cur cur.next;count;}return cur;}代码实现很简单cur遍历链表index-1次即可 具体插入步骤 1node.next prevIndex.next 2prevIndex.next node
这两行不能交换位置如果先让 prevIndex.next node那么就会丢失 index 位置的那个结点此时 node.next prevIndex.next 就相当于 node.next node代码会发生错误
完整代码 public void addIndex(int index, int value) {// 先检查index参数是否合法checkIndex(index);// 如果index 0头插即可if (index 0) {addFirst(value);return;}// 如果index size尾插即可if (index size()) {addLast(value);return;}// 中间插入删除Node node new Node(value);// 先找到index-1位置的结点Node prevIndex findPrevIndex(index);node.next prevIndex.next;prevIndex.next node;}4contains——判定是否包含某个元素
比较简单遍历这个数组即可 public boolean contain(int key) {Node cur head;while (cur ! null) {if (cur.value key) {return true;}cur cur.next;}return false;}因为这里我们存放的是 int 类型的变量但 LinkedList 当中可以存放引用数据类型的 ⚠️⚠️⚠️当表中是引用类型时就不可以用“等号”比较应该用 equals 方法 5 remove——删除第一次出现关键字为key的结点
1如果链表为空就不能再删了 2如果头结点就是要删除的 key 结点直接 head 存放下一个结点的地址 3如果链表其他结点是要删除的 key 结点要先找到 key 结点的前一个结点
5.1 findPrevKey——找到key结点的前一个结点 // 找到key的前一个结点public Node findPrevKey(int key) {Node cur head;while (cur.next ! null) {// 注意循环判断条件 如果cur.nextnull 说明cur此时是最后一个节点// 如果再访问下一个结点的value值会空指针异常// 此时的cur的value值在上一次循环以及判断过了所以cur走到最后一个结点时是最后一趟循环if (cur.next.value key) {return cur;}cur cur.next;}return null;}返回找到的这个结点即可 删除过程如图
当 key 结点的前一个结点的 next 不再存放 key 结点地址时key 结点此后不会再被使用会被系统自动回收
完整代码如下 public void remove(int key) {// 如果链表为空if (head null) {return;}// 如果头结点就是keyif (head.value key) {head head.next;return;}// 首先要找到key的前一个结点Node prevKey findPrevKey(key);if (prevKey null) {return;}// 重新链接Node del prevKey.next;prevKey.next del.next;}6 removeAll——删除所有值为key的结点
这里需要一个 prevCur 结点来记录 cur 的前一个结点 当 cur 是 key 结点时key结点的前一个结点也就是 prevCur可以直接断开和 key 结点的链接指向 key 结点的下一个
利用循环操作每个结点的 next 即可 public void removeAll(int key) {// 如果链表为空if (head null) {return;}Node prevCur head;Node cur head.next;while (cur ! null) {if (cur.value key) {prevCur.next cur.next;cur cur.next;} else {prevCur cur;cur cur.next;}}// 如果头结点就是keyif (head.value key) {head head.next;}}7size——获取单链表长度
直接遍历链表即可 public int size() {Node cur head;int count 0;while (cur ! null) {cur cur.next;count;}return count;}8clear——清空单链表
head 这个变量一直存放着链表的头结点位置把head置空就找不到此链表那么链表中的所有结点都会被系统自动回收 public void clear() {head null;}9display——打印链表
注意LinkedList 中不存在该方法为了方便看测试结果 public void disPlay() {Node cur head;while (cur ! null) {System.out.print(cur.value );cur cur.next;}System.out.println();}二、Java提供的LinkedList
1LinkedList 的说明
Java官方的集合框架中LinkedList 是一个普通的类继承了List接口 LinkedList 的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的结点中然后通过引用将结点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。
⚠️特殊说明 1 LinkedList 实现了List接口 2. LinkedList 的底层使用了双向链表 3. LinkedList 没有实现 RandomAccess 接口因此 LinkedList 不支持随机访问 4. LinkedList 的任意位置插入和删除元素时效率比较高时间复杂度为O(1) 5. LinkedList 比较适合任意位置插入的场景 2使用LinkedList
2.1LinkedList 实例化方式
1️⃣无参构造法 ArrayListInteger arrayList1 new ArrayList();3️⃣有参数——参数是其他 Collection Collection是集合框架中的一个接口实现了这个接口的类的对象就可以作为参数说白了就是 可以把其他的顺序表链表栈队列等等 作为参数传参例如 ArrayListInteger arrayList new ArrayList();arrayList .add(1);arrayList .add(2);LinkedListInteger linkedList new LinkedList(arrayList );我先 new 了一个顺序表对象 arrayList 在这个表中插入了 “1” “2” 两个数据顺序表中的数据是顺序存储的 当 arrayList 作为参数传递时linkedList 对象中就有了 arrayList 中的所有数据linkedList 中的数据是链式存储❗️的 2.2LinkedList 常用方法
在 main 方法中展示使用方式
public class Test {public static void main(String[] args) {LinkedListInteger linkedList new LinkedList();// 1插入默认是尾插linkedList.add(1);linkedList.add(2);linkedList.add(3);linkedList.add(4);linkedList.add(5);System.out.println(1尾插后 linkedList);// 2任意位置插入linkedList.add(0, -1);System.out.println(2在0位置插入后 linkedList);// 先new一个顺序表对象ArrayListInteger arrayList new ArrayList();arrayList.add(1);arrayList.add(2);arrayList.add(3);// 3插入其他Collection的所有元素尾插linkedList.addAll(arrayList);System.out.println(3插入arrayLsit所有数据后 linkedList);// 4删除任意位置的数据linkedList.remove(0);System.out.println(4删除0位置数据后 linkedList);// 5删除任意数据linkedList.remove(new Integer(1));System.out.println(5删除1后 linkedList);// 6获取任意位置的数据int ret linkedList.get(0);System.out.println(6获取0位置的数据 ret);// 7更改任意位置的数据linkedList.set(0, 100);System.out.println(7把0位置的数据更改为100后 linkedList);// 8查看链表中是否存在该数据boolean bl linkedList.contains(100);System.out.println(8查看链表中是否存在100这个数据 bl);// 9获取链表中任意数据第一次出现的位置int index linkedList.indexOf(3);System.out.println(93这个数据第一次出现的位置 index);// 10获取链表中任意数据最后一次出现的位置int lastIndex linkedList.lastIndexOf(3);System.out.println(103这个数据最后一次出现的位置 lastIndex);// 11截取ListInteger list linkedList.subList(1, 3);// 左闭右开System.out.println(11截取linkedList中从1到3的数据 list);// 12清空linkedList.clear();System.out.println(12清空linkedList后 linkedList);}
}运行结果
链表和顺序表对比 链表和顺序表都有各自的优缺点并且这两种结构的优缺点基本是互补的所以不存在哪一种结构更优秀只有在不同的场景会有更加合适的结构。 总结
以上就是今天分享的关于数据结构中【链表】的内容 一方面介绍了如何模拟实现简易的单链表 一方面介绍了Java集合框架中的 LInkedList 类的基本使用 并且分析了链表和顺序表的区别对比
如果本篇对你有帮助请点赞收藏支持一下小手一抖就是对作者莫大的鼓励啦 上山总比下山辛苦 下篇文章见
