Java-数据结构-链表-LinkedList（一） (^

本文主要是介绍Java-数据结构-链表-LinkedList（一） (^_−)☆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文本目录：

✿一、ArrayList的优点和缺陷：

✿二、链表：

❄️1、链表的概念与结构：

❄️2、单向不带头非循环链表的实现：

❄️（1）、操作：

▶display () 方法：

▶size()方法：

▶ contains(int key)方法：

▶addFirst(int data)方法：

▶ addLast(int data)方法：

▶addIndex(int index,int data)方法：

▶remove(int key)方法：

▶removeAllKey(int key)方法：

▶clear()方法：

§总结：

一、ArrayList的优点和缺陷：

优点：

对于ArrayList 来说，我们可以根据下标来访问任意元素，因为ArrayList 的底层是一个数组，所以可以做到。

缺陷：
当我使用ArrayList 时进行插入和删除呢，就需要移动后面的元素都进行往后移或者往前移动数据，才能做到，这样呢，时间复杂度最坏可以达到O(N)，所以会使效率非常的低下。

还有一点就是，我们当初识内存不够的时候，我们要扩容按照2倍或者1.5，但是呢，假如我们初识容量为20，但我们有21个元素，所以我们要扩容。是其达到2倍，就是400，但是呢，我们只有21个元素，剩下的大部分都浪费了，这就是个问题了。

所以当我们想要把这些缺陷解决的时候呢，我们引入了一格新的表，叫做链表，我们来看看什么是链表呢。

二、链表：

❄️1、链表的概念与结构：

链表呢从概念上来说呢，是一个物理存储结构上非连续存储结构，数据顺序的逻辑顺序是通过链表中的引用链接次序实现的。

链表是由一个个节点构成的，每一个节点都有两个结构，一个是数据一个是下一个节点的地址，我们来看看结构：

我们来看看链表是怎样存储的和其结构是什么样的：

这个呢，就是链表了。上图的链表呢也叫做：单向不带头非循环链表。

在这里呢我们把数值15的这个节点叫做头结点(head)，看到这里就有人有疑问了，这不是带头吗？为什么叫它不带头呢？我们来看看什么叫带头就知道了：

这个呢，才叫单向带头非循环链表。

那么什么是循环呢？我们来看什么才是循环链表：

这种的呢，才是循环链表。

链表的类型：

对于链表来说呢，我们有8中类型，分别是：

单向带头循环

单向带头非循环

单向不带头循环

单向不带头非循环

双向带头循环

双向带头非循环

双向不带头循环

双向不带头非循环

我们这次只需要了解到上面两个带红色字体的类型就可以了，因为这两种是最难的，这两种会了，其余的就简单了。

在我们的Java的底层的LinkedList就是双向不带头非循环链表

对于单向不带头非循环是在面试中常出现的。

❄️2、单向不带头非循环链表的实现：

我们写 单向不带头非循环链表 这个类是不是要有成员啊，我们的链表是由一个个的节点构成的，而节点呢又是一格完整的类，所以这里呢我们要用到内部类定义节点来实现，并且我们的MySingleList 这个类呢，要有一个head的节点的成员变量，我们俩看看怎么写：

我们把链表的方法都放到一个接口里，再由我们的类来实现接口中的方法，便于管理：

❄️（1）、操作：

▶display () 方法：

打印链表。我们先来看看原理是什么样的，之后再来看代码：

我们来看看代码的实现：

▶size()方法：

求链表的长度。这个方法和打印链表的方法是差不多的，我们这个方法就是需要在每次移动的时候呢，要记录长度。我们直接来看代码：

▶ contains(int key)方法：

在链表中查找链表中是否包含key这个值。其实这个也是非常简单的，和上面两个代码差不多的，只不过要每次都要判断cur.val是否和key相等就可以了，我们直接看代码：

▶addFirst(int data)方法：

头插法。我们来看看其思路是什么样的：

接下来我们来看看代码如何编写：

这个呢还是很简单的

▶ addLast(int data)方法：

尾插。我们还是先看尾插的思路：

这里我们要注意，当我们的链表为空的时候呢，我们直接把head = newNode

我们之后来看看代码是什么样的：

▶addIndex(int index,int data)方法：

在 index 这个位置插入 data 这个值。

1、在我们执行操作前呢，我们要先判断这个index值是否是合法的值，我们自定义一个异常来判断，我们来看：

2、对于index这个位置判断结束后，我们来想，当我们的index等于0时呢，是不是就相当于头插，在index等于链表的长度的时候呢，是不是就相当于尾插，所以这里我们可以这样写：

3、在处理完这些之后，我们就要对于在中间位置时进行处理了，我们来看看如何处理：

我们直接来看看思路是什么样的：

OK，我们来看看代码是如何实现的：

OK啊，我们的把其分为了三步，现在我们来看看这个方法的总代码：

▶remove(int key)方法：

删除key这个数值的节点。

对于这个操作呢，我们要先找到我们要删除的那个节点，之后进行删除操作，那么怎么做呢？我们来看看它是怎样删除的：

我们由上面这个图片就可以知道删除操作是怎样进行的了。那么我们想要删除key这个值的节点，我们是不是需要找到key这个节点之前的节点才能做到删除。

在写代码之前，我们要再思考一个问题啊，当我们链表为空，是不是需要直接返回，因为没有数据；再一个当我们的head.val就是key这个值是不是也要之间返回。在思考完这些问题之后，我们再来看看代码如何编写：

▶removeAllKey(int key)方法：

删除链表中所有的key这个数据的节点。

这个方法就比较麻烦了，我们要定义两个节点，一个是用来遍历链表查找和key相等的节点，另一个是用来删除节点的，我们来看看这两个接单是怎么配合的(这里比较复杂，认真看)：

但是呢，写到这里呢，还不是最严谨的，因为我们没有判断head.val是否和key相等。所以当我们判断上图的代码之后，我们还要添加一个关于判断head.val是否等于key的代码：

当然这样呢，我们的代码还是有一些缺陷的，我们在一开始就要判断head是不是空的，如果是空的话，就直接返回就可以了。

这样之后呢，我们的代码就完美了，让我们来看看最终的成果：

▶clear()方法：

清除链表的所有节点。

对于我们把节点删除，在这里呢，我们是不是只需要把每个节点中指向下一个节点地址设置为null就可以了呢。这里呢我们也是需要创建两个节点，一个呢用于删除节点，设置为null，另一个呢需要把要置为null的节点的地址存起来，防止我们在删除节点后，找不到下一个我们要删除的节点，我们来看思路的图片：

这样操作就可以了，之后我们来看看代码是怎样实现的：

这样呢，我们对于单向无头非循环的链表的自实现，就到这里就结束了，我们来看一遍我们的总代码：

public class MySingleList implements IList{//链表是由一个个节点组成的，每一个节点都是一个完整的对象//我们可以把节点用内部类构成static class ListNode {public int val;public ListNode next;public ListNode(int val) {//我们不用初始化地址this.val = val;}}//我们的MySingleList类的里面要有一个头节点的类public ListNode head;@Overridepublic void display() {ListNode cur = this.head;while(cur != null) {System.out.print(cur.val + "->");cur = cur.next;}System.out.println("");}@Overridepublic void addFirst(int data) {ListNode newNode = new ListNode(data);newNode.next = this.head;this.head = newNode;}@Overridepublic void addLast(int data) {ListNode newNode = new ListNode(data);if (this.head == null) {this.head = newNode;return;}//找尾巴ListNode cur = this.head;while(cur.next != null) {cur = cur.next;}cur.next = newNode;}private void indexExeption(int index) throws IndexException{int size = size();if (index < 0 || index > size) {throw new IndexException("index的位置错误");}}@Overridepublic void addIndex(int index, int data) {try {indexExeption(index);if (index == 0) {addFirst(data);}if (index == size()) {addLast(data);}//中间插入ListNode cur = this.head;while(index - 1 != 0) {index--;cur = cur.next;}ListNode newNode = new ListNode(data);newNode.next = cur.next;cur.next = newNode;}catch (IndexException e) {System.out.println("index位置异常");e.printStackTrace();}}@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}private ListNode findkeyListNode(int key) {ListNode cur = this.head;while(cur.next != null) {if (cur.next.val == key) {return cur;}cur = cur.next;}return null;}@Overridepublic void remove(int key) {if (this.head == null) {return;}if (this.head.val == key) {this.head = this.head.next;return;}ListNode cur = findkeyListNode(key);if (cur == null) {return;}ListNode del = cur.next;cur.next = del.next;}@Overridepublic void removeAllKey(int key) {if (this.head == null) {return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur != null) {if (cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if (this.head.val == key) {this.head = this.head.next;}}@Overridepublic int size() {ListNode cur = this.head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {ListNode cur = this.head;while(cur != null) {ListNode curNext = cur.next;cur.next = null;cur = curNext;}this.head = null;}
}