【数据结构_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;}}（剩下的明天写）