java学习之数据结构：二、链表
本节介绍链表
目录
1.什么是链表
1.1链表定义
1.2链表分类
2.链表实现
2.1创建链表
1）手动创建
2）创建链表类进行管理链表的相关操作
2.2添加元素
1）头插法
2）尾插法
3）任意位置插入
2.3删除
2.4查找
1）返回节点
2）返回索引
1.什么是链表
1.1链表定义
链表是一种数据结构，它由一系列节点组成。每个节点包含至少两部分信息：数据域（用于存储数据元素）和指针域（用于存储指向下一个节点的引用或地址）。链表通过节点之间的指针连接，形成一个链式结构。
与数组不同：1.数组中的元素在内存中是连续存储的，而链表的节点在内存中的存储位置不一定是连续的。2.链表它在插入和删除操作上相对数组更加灵活
1.2链表分类
- 单向链表：也称为单链表，是最基本的链表形式。每个节点只包含一个指向下一个节点的指针，只能从链表的头节点开始，沿着指针依次访问后续节点，无法反向遍历。
- 双向链表：在双向链表中，每个节点除了有一个指向后继节点的指针外，还有一个指向前驱节点的指针。这使得双向链表可以在两个方向上进行遍历，既可以从头节点向后遍历，也可以从尾节点向前遍历。
- 循环链表：循环链表又分为单向循环链表和双向循环链表。单向循环链表的尾节点的指针指向头节点，形成一个环形结构，这样可以从任意一个节点出发，遍历整个链表。双向循环链表则是头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，同样实现了环形的结构，提供了更灵活的遍历方式。
2.链表实现
2.1创建链表
1）手动创建
即自己创建一个node类然后调用
package com.qcby;public class Node {Node next;int value;public static void main(String[] args) {Node node1 = new Node();node1.value = 1;Node node2 = new Node();node2.value = 2;node1.next = node2;System.out.println(node1.value);System.out.println(node1.toString());}public String toString() {return "Node[" +"next=" + next +", value=" + value +']';}
}
2）创建链表类进行管理链表的相关操作
使用 LinkList list = new LinkList(); 创建链表
2.2添加元素
1）头插法
头插法就是每次有一个新的元素进入链表时，将新节点插入到链表的头部，使其成为新的头节点。
代码如下：
public void addHead(int value) {Node node=new Node(value);if(head==null) {head=node;return;}node.next=head;head=node;}2）尾插法
当每次链表接受新的元素时，将新节点插入到链表的尾部，使其成为新的尾节点。
代码如下：
public void add(int data) {Node node = new Node();node.value = data;if (head == null) {head = node;} else {Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = node;}}3）任意位置插入
在接收到新元素时，给新元素的位置做规定，即任意位置插入是将新节点插入到链表的指定位置。
代码：
public void addIndex(int index, int data) {Node node = new Node();node.value = data;if (index < 0 || index > getLength()) {System.out.println("超出范围");return;}if (index == 0) {addHead(data);} else {Node temp = head;for (int i = 0; i < index - 1; i++) {temp = temp.next;}node.next = temp.next;temp.next = node;}}注意：想要实现任意位置插入，需要关注其链表长度，防止该插入位置比链表长度大出现问题
即实现一个求解长度的类，主要是通过遍历链表节点来记录长度：
public int getLength() {int length = 0;Node temp = head;while (temp != null) {length++;temp = temp.next;}return length;}2.3删除
public void remove(int data) {if (head == null) {System.out.println("链表为空");return;}if (head.value == data) {head = head.next;return;}Node temp = head;while (temp.next != null) {if (temp.next.value == data) {temp.next = temp.next.next;return;}temp = temp.next;}}2.4查找
1）返回节点
public Node find(int data) {Node temp = head;while (temp != null) {if (temp.value == data) {return temp;}temp = temp.next;}return null;}2）返回索引
public int findIndex(int data) {Node temp = head;int index = 0;while (temp != null) {if (temp.value == data) {return index;}temp = temp.next;index++;}return -1;}