(67条消息) 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删除头节点和尾节点

 

本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。