当前位置：首页 > news >正文

数据结构之链表

news 2025/8/4 9:36:10

链表

逻辑有序，内存无序，链式存储

单向链表

单向链表结构图

代码实现

package org.example.data.structure.linklist;import java.util.Objects;/*** 单向链表的实现** @author xzy* @since 2024/8/31 17:37*/
public class SingleLinkList {/*** 初始化一个头节点: data域为空, next指向第一个节点开始*/private PersonNode headNode = new PersonNode();/*** 是否空链表*/public Boolean isEmpty() {return headNode.getNext() == null;}/*** 是否是最后一个节点*/public Boolean isLastNode(PersonNode node) {return node.getNext() == null;}/*** 从头节点开始向后遍历, 找见最后一个节点进行插入*/public void add(Person person) {PersonNode node = headNode;while (node.getNext() != null) {// 下一个节点node = node.getNext();}// 新节点PersonNode newNode = new PersonNode(null, person);node.setNext(newNode);}/*** 根据Id删除节点, 只考虑了ID作为唯一标识的场景, 即ID唯一键*/public void delete(Integer id) {if (isEmpty() || id == null) {return;}PersonNode node = headNode;while (true) {PersonNode next = node.getNext();if (Objects.equals(next.getData().getId(), id)) {// 判断是否是最后一个节点if (isLastNode(next)) {node.setNext(null);} else {node.setNext(next.getNext());}break;} else {if (isLastNode(node)) {break;}node = node.getNext();}}}/*** 修改*/public void update(Person person) {if (isEmpty() || Objects.isNull(person) || Objects.isNull(person.getId())) {return;}PersonNode node = headNode;while (true) {Person data = node.getData();// 考虑首节点if (Objects.nonNull(data) && Objects.equals(data.getId(), person.getId())) {data.setName(person.getName());break;} else {if (isLastNode(node)) {break;}node = node.getNext();}}}/*** 获取链表所有的数据*/public Person[] getList() {if (headNode.getNext() == null) {System.out.println("空链表");return null;}Person[] result = new Person[10];int i = 0;PersonNode temp = headNode.getNext();while (true) {Person data = temp.getData();result[i] = data;if (temp.getNext() != null) {temp = temp.getNext();i++;} else {break;}}// 省略去除null的操作return result;}
}

双向链表

出现的原因：

单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助(前一个)节点，而双向链表，则可以自我删除。

代码实现

package org.example.data.structure.linklist;import java.util.Objects;/*** @author xzy* @since 2024/9/1 17:16*/
public class DoubleLinkList {/*** 头节点*/private PersonDoubleNode headNode = new PersonDoubleNode();/*** 是否是空链表*/public Boolean isEmpty() {return headNode.getNext() == null;}/*** 是否是尾节点*/public Boolean isLastNode(PersonDoubleNode node) {return node.getNext() == null;}/*** 添加节点(默认插入到最后一个节点)*/public void add(Person person) {PersonDoubleNode temp = headNode;while (true) {if (isLastNode(temp)) {PersonDoubleNode newNode = new PersonDoubleNode(person, temp, null);temp.setNext(newNode);break;} else {temp = temp.getNext();}}}/*** 删除元素*/public void delete(Integer id) {if (isEmpty()) {System.out.println("空链表");return;}PersonDoubleNode temp = headNode;while (true) {if (Objects.nonNull(temp.getData()) && Objects.equals(temp.getData().getId(), id)) {PersonDoubleNode pre = temp.getPre();PersonDoubleNode next = temp.getNext();pre.setNext(next);if (!isLastNode(temp)){next.setPre(pre);}break;} else {if (!isLastNode(temp)) {temp = temp.getNext();} else {break;}}}}/*** 修改元素*/public void update(Person person) {if (isEmpty()) {System.out.println("空链表");return;}PersonDoubleNode temp = headNode;while (true) {if (Objects.nonNull(temp.getData()) && Objects.equals(temp.getData().getId(), person.getId())) {temp.setData(person);break;} else {if (!isLastNode(temp)) {temp = temp.getNext();} else {break;}}}}/*** 获取链表所有元素*/public Person[] getList() {if (isEmpty()) {System.out.println("空链表");return null;}Person[] people = new Person[10];int i = 0;PersonDoubleNode temp = headNode.getNext();while (true) {people[i] = temp.getData();if (isLastNode(temp)) {break;} else {temp = temp.getNext();i++;}}return people;}
}