【数据结构】 链表简介与单链表的实现

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;}

总结

关于《【数据结构】 链表简介与单链表的实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！