手机网站建设免费空间,网络舆情监测分析,做机网站,wordpress分享到文章目录 ArrayList的缺陷链表链表的概念及结构链表的分类单向或者双向带头或者不带头循环或者非循环 单链表的实现创建单链表遍历链表得到单链表的长度查找是否包含关键字头插法尾插法任意位置插入删除第一次出现关键字为key的节点删除所有值为key的节点回收链表 总结 ArrayLi… 文章目录 ArrayList的缺陷链表链表的概念及结构链表的分类单向或者双向带头或者不带头循环或者非循环 单链表的实现创建单链表遍历链表得到单链表的长度查找是否包含关键字头插法尾插法任意位置插入删除第一次出现关键字为key的节点删除所有值为key的节点回收链表 总结 ArrayList的缺陷
在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用并且进行了简单模拟实现。通过源码知道ArrayList底层使用数组来存储元素
由于其底层是一段连续空间当在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。 因此java集合中又引入了LinkedList即链表结构。
链表
链表的概念及结构
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的
就如同火车中间通过链条链接的一个道理
链表的大概结构如下所示 链表的每一节都含有相应的数据与下一节的地址一般我们会记录起始节点可以用来我们访问该链表最后一个节点不含有下一节点的地址置为null
链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
单向或者双向 带头或者不带头 循环或者非循环 虽然有这么多的链表的结构但是我们重点掌握两种:
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多 无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
单链表的实现
接下来我们来实现一个无头单向非循环链表实现并实现一些相应的功能
创建单链表
博主在这里创建一个类为MyLinkedList类我们将在这里面实现我们的无头单向非循环链表
创建单链表其实很简单我们需要建立一个类类里面放你需要放的数据元素以及该类类型的元素用于储存下一节点的地址
然后我们还需要一个变量来记录其实节点在这里我们用一个内部类在MyLinkedList类进行表示并在createLink方法里进行各个节点的创建并赋值然后将这些节点链接起来 代码实现如下
public class MyLinkedList {class Node {public int val;public Node next;public Node(int val) {this.val val;}}public Node head;// 代表当前链表的头节点的引用public void createLink() {Node node1 new Node(11);Node node2 new Node(22);Node node3 new Node(33);Node node4 new Node(44);node1.next node2;node2.next node3;node3.next node4; /* */head node1;}
}遍历链表
写好的链表我们来进行打印一下看看是否创建成功
我们的head为我们的头节点也就是我们遍历的起点但是由于该单链表是单向的如果使用头节点进行遍历的话会导致后面找不到头节点所以我们这里重新创建一个变量进行遍历。
由于每一节点里的next里面都存储着我们下一节点的地址所以当我们访问完当前节点的元素后将当前节点的next赋给我们所创建的遍历变量即可
由于最后一个节点里next里面为null所以我们将它作为结束条件
代码实现如下
public void disPlay() {Node sur head;while(sur ! null) {System.out.print(sur.val );sur sur.next;}}得到单链表的长度
进行遍历并用一个数进行记录最后进行返回就行
代码实现如下 public int size(){int count 0;Node cur head;while (cur ! null) {count;cur cur.next;}return count;}
查找是否包含关键字
我们只需要对该链表进行遍历然后一一比对就好大致实现过程与遍历链表相同
代码实现如下 //查找是否包含关键字key是否在单链表当中public boolean contains(int key){Node cur head;while (cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}头插法
将第一个节点赋给我们新添加的节点里面的next
并且将新添加的节点赋给head作为新的头节点
代码实现如下 public void addFirst(int data){Node node new Node(data);node.next head;head node;}注意一定要注意赋值的顺序
尾插法
我们首先对该链表进行遍历当遍历到最后一个节点时
将最后一个节点里的next赋为我们新增的节点即可。
如果该链表为空直接将该新增节点设为头节点就好
代码实现如下 public void addLast(int data){Node node new Node(data);if(head null) {head node;return;}Node cur head;while (cur.next ! null) {cur cur.next;}cur.next node;}任意位置插入
首先我们需要对需要插入的位置进行遍历必须为合法如果不合法我们会抛出一个异常进行提醒这里我们自定义了一个异常如下
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
}
任意位置插入我们可以分为种情况
插在开头插在结尾插在中间
前两种我们已经实现了我们现在只需要实现插在中间就好
我们对该单链表进行编号第一个节点为我们的0下标。我们需要遍历单链表找到所需要插入下标的前一个节点
将该节点的next设为我们新增的节点将新增节点里面的next设为下一节点 代码实现如下 //任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data)throws ListIndexOutOfException{checkIndex(index);if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;}Node cur findIndexSubOne(index);Node node new Node(data);node.next cur.next;cur.next node;}/*** 找到 index-1位置的节点的地址* param index* return*/private Node findIndexSubOne(int index) {Node cur head;int count 0;while (count ! index-1) {cur cur.next;count;}return cur;}private void checkIndex(int index) throws ListIndexOutOfException{if(index 0 || index size()) {throw new ListIndexOutOfException(index位置不合法);}}删除第一次出现关键字为key的节点
分为四种情况
一个节点都没有删除数据在第一个没有你要删除的数据有你要删除的数据且不是第一个
第一种情况判断是否为空后直接返回就好
第二种情况直接将头节点置为下一节点也就时headhead.next
第三种情况遍历单链表后返回就好
第四种情况找到所需要删除数据的前一节点将所需要删除数据的前一节点的next设为当前需要删除数据节点的next
代码实现如下
//删除第一次出现关键字为key的节点 O(N)public void remove(int key){if(head null) {return ;//一个节点都没有}if(head.val key) {head head.next;return;}Node cur searchPrev(key);if(cur null) {return;}Node del cur.next;//要删除的节点cur.next del.next;}/*** 找到关键字key的前一个节点* param key* return*/private Node searchPrev(int key) {Node cur head;while (cur.next ! null) {if(cur.next.val key) {return cur;}cur cur.next;}return null;//没有你要删除的节点}删除所有值为key的节点
我们依旧需要对该单链表进行判断如果为空就直接返回
由于我们需要删除很多个这样的节点但是我们的单链表却是单向的按照上面的写法我们则需要遍历很多次单链表大大的增加了复杂度我们为了降低时间复杂度使它降为O(N);
我们设两个遍历节点进行遍历一个在前为cur一个在后prev
前面的cur负责进行遍历删除后面的prev负责跟在cur后面记录cur的上一节点
当cur下一节点不是我们所要删除的元素时这时候我们将prev变为我们当前节点的cur而cur变为当前节点的next 当前的删除方法只能删除第一个节点以后的元素所以我们还需要处理第一个元素是我们所需要删除的情况。
代码实现如下
//删除所有值为key的节点public void removeAllKey(int key){if(head null) {return;}Node prev head;Node cur head.next;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 void clear() {head null;}总结
关于《【数据结构】 链表简介与单链表的实现》就讲解到这儿感谢大家的支持欢迎各位留言交流以及批评指正如果文章对您有帮助或者觉得作者写的还不错可以点一下关注点赞收藏支持一下
