[数据结构] 链表
目录
1.链表的基本概念
2.链表的实现 -- 节点的构造和链接
节点如何构造?
如何将链表关联起来?
3.链表的方法(功能)
1).display() -- 链表的遍历
2).size() -- 求链表的长度
3).addFirst(int val) -- 头插法
4).addLast(int val) -- 尾插法
5).addIndex -- 在任意位置插入
6).contains(int val) -- 链表中是否包含某个元素
7). remove(int key) -- 删除第一次出现的关键字的节点
8).removeAll(int val) -- 删除所有出现的关键字的节点
9).clear() -- 清空
回收对象,防止浪费 : head == null;
1.链表的基本概念
- 链表（Linked List）是一种常见的基础数据结构，它由一系列节点（Node）组成，每个节点包含两部分：一部分存放数据元素，另一部分存放指向下一个节点的指针.
2.链表的实现 -- 节点的构造和链接
节点如何构造?
在 Java 中，通常通过定义一个类来表示链表中的节点。每个节点通常包含两个部分：数据域和指针域。对于单向链表，每个节点的指针域指向下一个节点.
public class LinkedList {
// 定义链表节点
static class ListNode {
int val; // 数据域
ListNode next; // 指针域
ListNode(int x) {
this.val = x;
this.next = null;
}
}
public ListNode head;
}如何将链表关联起来?
通过访问node1的指针域next,将其赋值为下一个节点的地址,以此类推,最后让头节点head指向第一个节点node1.
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1;3.链表的方法(功能)
1).display() -- 链表的遍历
首先，我们创建一个名为 cur 的局部变量，它是一个指向 ListNode 类型的引用。将链表的头节点（head）赋值给 cur，这样我们就有了一个可以用来遍历整个链表的起始点.使用 while 循环来遍历链表。只要 cur不是 null（即还没有到达链表的末尾），就继续执行循环体内的代码。如果 cur 是 null，则说明已经到了链表的末尾，循环结束。在循环体内，我们使用 System.out.print 来打印当前节点的数据。这里用 + " -> " 格式化输出，以箭头分隔各个数据项，直观地表示出它们之间的链接关系。更新 cur指针，使其指向下一个节点（通过 cur.next 获取）。这一步非常重要，因为它确保了我们在下一次迭代时能够访问链表中的下一个节点。当循环结束后，我们额外打印一个 null，表示链表的终止。这是为了更清晰地展示链表结构，表明没有更多的节点了。
public void display() {
ListNode cur = head;
while(cur != null) {
System.out.print(cur.val + "->");
cur = cur.next;
}
System.out.println("null");
}2).size() -- 求链表的长度
定义count变量,记录cur向后走的次数,每走一步,count++
public int size() {
ListNode cur = head;
int count = 0;
while(cur != null) {
count++;
cur = cur.next;
}
return count;
}3).addFirst(int val) -- 头插法
1. 将head头节点的地址传给node.next 2. 然后让head指向node
注意: 这里两步的顺序不可以交换 , 否则 就是自己指向自己了
public void addFirst(int val) {
ListNode node = new ListNode(val);
node.next = head;
head = node;
}4).addLast(int val) -- 尾插法
1.为了避免head == null 报错, 先进行判断,若head == null , 则 head = node,然后return掉.
2.若head != null , 则 这通过循环找到 cur.next == null ,最后让cur.next = node.
public void addLast(int val) {
ListNode node = new ListNode(val);
if(head == null) {
head = node;
return;
}
ListNode cur = head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}5).addIndex -- 在任意位置插入
1.判断index的合法性: (1). 定义一个 checkIndex(int index) 方法用来检查 index 的合法性
2.index == 0 || index == size();前者相当于是头插，直接调用 addFirst(),后者相当于是尾插，直接调用 addLast()
3.找到 index 的前一个位置,创建一个 findIndexSubOne(int index) 方法,创建一个节点 cur 来接收调用方法的返回值, 最后 cur 就是 index 位置的前一个节点了
4.进行连接,实例化一个所带数据为 val 的节点 node,
node.next = cur.next;
cur.next = node;
public void addIndex(int index,int val) {
// 1.判断index的合法性
try {
checkIndex(index);
} catch(IndexNotLegalException e) {
e.printStackTrace();
}
// index == 0 || index == size()
if(index == 0) {
addFirst(val);
return;
} else if(index == size()) {
addLast(val);
return;
}
// 3.找到index前一个位置
ListNode cur = findIndexSubOne(index);
// 4.进行连接
ListNode node = new ListNode(val);
node.next = cur.next;
cur.next = node;
}
public ListNode findIndexSubOne(int index) {
ListNode cur = head;
for (int i = 0; i < index - 1; i++) {
cur = cur.next;
}
return cur;
}
public void checkIndex(int index) {
if(index < 0 || index >size()) {
throw new IndexNotLegalException("index位置不合法");
}
}
public class IndexNotLegalException extends RuntimeException {
public IndexNotLegalException() {
}
public IndexNotLegalException(String message) {
super(message);
}
}6).contains(int val) -- 链表中是否包含某个元素
遍历链表,如果能在链表中找到val,则返回true,否则,返回false
public boolean contains(int val) {
ListNode cur = head;
while(cur != null) {
if(cur.val == val) {
return true;
}
cur = cur.next;
}
return false;
}7). remove(int key) -- 删除第一次出现的关键字的节点
1.首先判断链表是否为空
2.循环遍历 : cur.next != null
3.找到val值的前一个节点cur : 当cur.next.val = val 时,找到目标
4.进行删除
public void remove(int key) {
// 如果链表为空
if(head == null) {
return;
}
// 如果第一个元素就为val时
if(head.val == key) {
head = head.next;
return;
}
ListNode cur = head;
while(cur.next != null) {
if(cur.next.val == key) {
cur.next = cur.next.next;
return;
}
cur = cur.next;
}
}8).removeAll(int val) -- 删除所有出现的关键字的节点
- 定义两个引用变量
- cur 代表当前需要删除的节点
- prev 代表当前需要删除节点的前驱
- 若
cur.val == val
prev.next = cur.nextcur = cur.next- 否则：
prev = curcur = cur.next- 处理头节点
public void removeAll(int key) {
if(head == null) {
return;
}
ListNode prev = head;
ListNode cur = head.next;
while(cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
// 除了头节点都删除完成
if(head.val == key) {
head = head.next;
}
}9).clear() -- 清空
回收对象,防止浪费 : head == null;
public void clear() {
this.head = null;
}