概述
- 链表在内存中的存储形式
- 链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上
- 链表有节点组成,每个节点又分成两个部分:1)数据域 (data) 2)指针域
- 头节点(head)
- 链表需要创建一个头节点来指定头,该节点数据域为null,指针初始化为null
- 当第一个节点加入时,将头节点的指针指向第一个节点
- 头节点只具有指向作用
- 链表又分为
![链表.png](https://cdn.nlark.com/yuque/0/2023/png/35542336/1680266642597-71c0bd98-478e-48ae-9017-b14458930b48.png#averageHue=%23b6b5b5&clientId=ub4455fe5-ae4c-4&from=ui&id=u415bda15&name=%E9%93%BE%E8%A1%A8.png&originHeight=466&originWidth=596&originalType=binary&ratio=1.25&rotation=0&showTitle=false&size=27372&status=done&style=shadow&taskId=u39d296da-5c42-4e59-af58-752089c055c&title=)
单链表
![单链表.png](https://cdn.nlark.com/yuque/0/2023/png/35542336/1680058136752-37bfecb8-239e-4d06-8c30-2460a6325c89.png#averageHue=%23fafafa&clientId=uf67361e3-0b1e-4&from=ui&id=u0670e10e&name=%E5%8D%95%E9%93%BE%E8%A1%A8.png&originHeight=348&originWidth=1080&originalType=binary&ratio=1.25&rotation=0&showTitle=false&size=23147&status=done&style=shadow&taskId=ue1e55f3b-d716-4f9b-a330-8b2f3165a4e&title=)
/**
* @author 发着呆看星
* @create 2023/3/29
**/
public class Node<E> {
// 节点id
private int no;
// 数据域
private E data;
// 指针域,指向下一个节点
public Node<E> next;
public Node(int no, E data) {
this.no = no;
this.data = data;
}
public Node() {
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", data=" + data +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node<?> node = (Node<?>) o;
return no == node.no;
}
@Override
public int hashCode() {
return Objects.hash(no);
}
}
/**
* @author 发着呆看星
* @create 2023/3/29
**/
public class SingleLinkedList<E> {
// 创建头节点 ,只具有指向功能
/*
也可以没有 ,加入的第一个节点即为头节点
private Node<E> head = null; 加入第一个时判断 ,head = 第一个节点
*/
private Node<E> head = new Node<>();
// 去重添加节点操作,添加至链表末尾
public void addNode(Node<E> node) {
Node<E> temp;
if (head.next == null) {
head.next = node;
return;
}
if (head.next.equals(node)) {
System.out.println("链表中已存在该元素");
return;
} else {
temp = head.next;
}
while (true) {
if (temp.equals(node)){
System.out.println("链表中已存在该元素");
return;
}
if (temp.next == null) {
temp.next = node;
break;
}
temp = temp.next;
}
}
// 遍历链表
public void showLinkedList() {
if (head.next == null) {
System.out.println("当前链表为空");
return;
}
Node<E> temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
// 删除指定节点
// 单链表删除节点应该找到要删除节点的前一个节点
public void delete(int no){
if (head.next == null){
System.out.println("当前链表没有元素,不能进行删除操作");
return;
}
Node<E> temp = head;
while (temp.next != null){
if (temp.next.getNo() == no) {
temp.next = temp.next.next;
return;
}
temp = temp.next;
}
System.out.println("链表中没有你想要删除的元素");
}
// 修改节点
public void update(Node<E> node){
if (head.next == null){
System.out.println("当前链表没有元素,不能进行修改操作");
return;
}
Node<E> temp = head.next;
while (temp != null){
if (temp.getNo() == node.getNo()){
temp.setData(node.getData());
return;
}
temp = temp.next;
}
System.out.println("当前链表没有你想要修改的节点");
}
}
public static void main(String[] args) {
SingleLinkedList<String> sll = new SingleLinkedList<>();
boolean loop = true;
Scanner scanner = new Scanner(System.in);
int no;
while (loop){
System.out.println("==================================");
System.out.println("(a):添加节点");
System.out.println("(u):修改节点");
System.out.println("(r):删除指定节点");
System.out.println("(l):查看链表");
System.out.println("(e):退出程序");
System.out.print("请选择你要的操作:");
char c = scanner.next().charAt(0);
switch (c){
case 'a':
case 'u':
System.out.print("请输入节点的编号:");
no = scanner.nextInt();
System.out.print("请输入节点的数据:");
String data = scanner.next();
Node<String> stringNode = new Node<>(no,data);
sll.addNode(stringNode);
break;
case 'r':
System.out.print("请输入想要删除节点的编号:");
no = scanner.nextInt();
sll.delete(no);
break;
case 'l':
sll.showLinkedList();
break;
case 'e':
loop = false;
break;
}
System.out.println();
}
}
双链表
- 双链表有两个指针域,一个指向上一个节点 ,一个指向下一个节点
- 第一个节点指向上一个节点的指针域为null
- 最后一个节指向下一个节点的指针域为null
![双链表.png](https://cdn.nlark.com/yuque/0/2023/png/35542336/1680058388169-72dfc20d-f5a2-44e0-9e1f-385aa99db6fc.png#averageHue=%23f9f8f8&clientId=uf67361e3-0b1e-4&from=ui&id=ub39ab239&name=%E5%8F%8C%E9%93%BE%E8%A1%A8.png&originHeight=250&originWidth=1080&originalType=binary&ratio=1.25&rotation=0&showTitle=false&size=28484&status=done&style=shadow&taskId=u245aa12c-dde5-466b-aff9-352349acd71&title=)
循环链表
- 和普通链表不同的是,循环链表的最后一个节点的 next 指向 第一个节点
![循环链表.png](https://cdn.nlark.com/yuque/0/2023/png/35542336/1680058663156-74cbfdc0-0dc8-44b4-8540-8d390e0dbbaa.png#averageHue=%23f7f7f7&clientId=uf67361e3-0b1e-4&from=ui&id=uc22bb8b2&name=%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8.png&originHeight=440&originWidth=514&originalType=binary&ratio=1.25&rotation=0&showTitle=false&size=36197&status=done&style=shadow&taskId=ub86c7693-ce99-462a-82de-bdea71c3050&title=)