JAVA——链表

一、链表概念及结构

链表：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。如下图：（通俗的说：就是由一个个节点组成，这些节点逻辑上连续，物理上不连续）

类比火车：

singleLinkedList ——火车车次（一整个火车or哪趟火车）

Node——车厢，具体储存元素的类，每个单链表的节点就是Node的一个对象

Node.head ；——当前链表的头节点（只要知道头节点就可以此访问链表中的所有节点）

int  size ；——当前链表的长度（节点个数），保存有效数据的个数

画图理解：

class  Node {
       int  val ;  //储存节点的值
       Node next ;  //表示下一个节点的地址
       //这里为什么使用Node引用，单链表的所有节点都是Node类的对象
       
}
      Node node = new Node（）;//创建一个新节点
      node.val =1 ;//值为1，地址为空，就没写
      //与其他节点进行连接
      Node node1 = new Node（）; //创建名为node1的新节点
      node1.val = 2 ; //值为2
      node.next = node1 ；//让第一个结点的next储存下一个结点的地址

二、链表的实现方法 

※注意事项：

①单链表中头节点很烦人，不论是插入还是删除均需考虑头节点，因为其没有前驱。

②所有的点 *** 作（"."）均需注意空指针情况

2.1头插法

利用虚拟头节点的办法：

虚拟头节点：——dummyHead，只作为链表的头节点使用，不储存有效数据即size的长度没变，这样链表中的其他有效节点我们可以一视同仁，都有头节点

 

2.2在任意位置插入

利用虚拟头节点的办法：

2.3在链表尾部插入

2.4查找第一个值为val的值的索引

2.5查找是否包含val值

2.6查找索引为index位置的节点值

2.7将index位置的元素节点值修改为newVal

 2.8删除链表中第一个值为val的元素

2.9 删除链表中所有值为val的节点

 

利用虚拟头节点的方法：

2.10删除index位置的节点并返回该节点删除前的值

利用虚拟头节点的方法： 

 2.11删除头节点和尾节点