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的节点
分为四种情况
- 一个节点都没有
- 删除数据在第一个
- 没有你要删除的数据
- 有你要删除的数据且不是第一个
第一种情况判断是否为空后直接返回就好
第二种情况直接将头节点置为下一节点，也就时head=head.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; }
总结
关于《【数据结构】 链表简介与单链表的实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！
