【数据结构_4下篇】链表

一、链表的概念

链表，不要求在连续的内存空间，链表是一个离散的结构。

链表的元素和元素之间，内存是不连续的，而且这些元素的空间之间也没有什么规律：

1.顺序上没有规律 2.内存空间上也没有规律

*如何知道链表中包含元素以及如何遍历链表中的所有元素呢？

链表中的每一个节点都包含两个部分，一个是他自身的引用变量，另一个是next（下一个节点的引用变量），因此只要我们拥有第一个节点的引用变量，我们就可以完成上述操作了

链表的两个特点：

1.链表的元素是在离散的内存空间上的

2.每个元素都记录下一个元素的地址（引用）

由此可见，链表的第一个元素是非常重要的，因此，在习惯上我们也经常用链表的第一个节点来代指整个链表。

二、各种类型的链表

1.单向的链表

单向链表根据顺序只能知道下一个，不能知道上一个。

2.双向链表

双向链表，每个节点包含两个引用，prev和next

双向链表的功能性更强，但是他消耗的空间也比单向链表大了

3.无傀儡节点的链表

(head为引用)

头节点：链表的第一个节点

傀儡节点：这个节点并不用来存储数据，而只是用来占个位子，来简化后续代码的编写~~把链表的第一个节点作为傀儡（dummy）

通过head引用指向第一个节点，此时这个链表是不带傀儡节点的，通过head引用拿到的第一个节点就是第一个元素

4.有傀儡节点的链表

此时这个链表是带傀儡节点的

通过head引用指向傀儡节点，通过head.next拿到的才是第一个元素

*引入傀儡节点，是为了简化代码

5.非循环链表

最后一个节点的next指向的是null，说明这个链表不是循环的

6.循环链表

最后一个节点的next指向的是第一个节点，这个链表是循环的

三、模拟实现LinkedList

1.创建节点

//要想实现链表的基本功能，首先要表示链表的一个节点
//对于节点这个类来说，他的本身功能单一，比较简单
//如果高一些get set 方法 ，后续代码就会显得很难看class Node{public String value;//节点保存的值public Node next;//这个节点的下一个元素public Node(String value, Node next) {this.value = value;this.next = null;}//当我们创建一个Node的时候，就创建好了链表的头节点，此时链表头节点的值可以确定，且尚未含有下一个节点
}
//这是一个单链表的节点 双向链表还需要一个prev

2.创建头节点

public class MyLinkedList {//把链表的头节点表示出来，此时整个链表就都能被获取到了//此处不包含傀儡系欸但，head== null 的时候表示空的链表private Node head = null;}

3.实现具体功能

//1.链表的头插操作

newNode.next =head;

head = new Node;

    //1.链表的头插操作public void addFirst(String value){Node newNode = new Node(value);newNode.next =head;head = newNode;//head只是一个引用类型！！！}

4.遍历链表

    //2.遍历链表的操作public String toString(){StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (Node cur = head;cur!= null; cur= cur.next) {stringBuilder.append(cur.value);if(cur.next!= null) {stringBuilder.append(",");}}stringBuilder.append("]");return stringBuilder.toString();}

5.尾插节点（*不要忘记特殊的情况 head == null!）

    public void addLast( String value){//1.首先找到最后一个节点Node tail = head;//*还要考虑特殊的情况if(head == null){Node node = new Node(value);head = node;return;}for (;tail.next!=null; tail = tail.next) {if(tail.next==null){break;}}//此时的tail也就是我们要找的最后一个节点Node node = new Node(value);tail.next = node;node.next = null;}}

（剩下的明天写）