单链表:
每个数据是以节点的形式存在的
每个节点分为数据域和指针域
数据域中保存该节点的数据
指针域中保存指向下一个节点的指针
实现思路:
节点类SingleNode中保存数据和指向下一个节点的指针
单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法
对于链表方法,涉及到位置查找,如在指定位置增加、删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置。
对于节点的增加删除,只需要修改相关结点的指针指向即可
代码实现:
节点类SingleNode:
public class SingleNode {
public int data;
public SingleNode next;
public SingleNode(int data) {
this.data = data;
}
@Override
public String toString() {
return "SingleNode{" + "data=" + data + '}';
}
}
单链表类SingleLinkedList:
public class SingleLinkedList {
private SingleNode head = new SingleNode(0);
//获取头结点
public SingleNode getHead(){
return head;
}
//添加节点
public void add(SingleNode singleNode) {
SingleNode temp = head;
//找到链表最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = singleNode;
}
//按顺序添加节点
public void addByOrder(SingleNode singleNode) {
SingleNode temp = head;
while (true) {
if (temp.next == null) {
//已经遍历到链表最后了
break;
} else if (temp.next.data > singleNode.data) {
//找到应插入的位置
break;
}
temp = temp.next;
}
singleNode.next = temp.next;
temp.next = singleNode;
}
//删除节点
public void delete(int data) {
SingleNode temp = head;
boolean flag = false; //标志是否找到待删除节点的前一个节点
while (true) {
if (temp.next == null) {
//已经遍历到链表最后了
break;
} else if (temp.next.data == data) {
//找到待删除节点的前一个节点
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("要删除的节点不存在");
}
}
//输出链表
public void show() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
SingleNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
}
双向链表:
每个节点中除了保存了指向后一个节点的指针外,还保存了指向前一个节点的指针
实现思路:
相关方法实现与单链表类似,不同点在于需要增加对指向前一个节点的指针的更改
代码实现:
节点类DoubleNode:
public class DoubleNode {
public int data;
public DoubleNode next;
public DoubleNode pre;
public DoubleNode(int data) {
this.data = data;
}
@Override
public String toString() {
return "DoubleNode{" + "data=" + data + '}';
}
}
双向链表类DoubleLinkedList:
public class DoubleLinkedList {
public DoubleNode head = new DoubleNode(0);
//获取头结点
public DoubleNode getHead() {
return head;
}
//添加节点
public void add(DoubleNode doubleNode) {
DoubleNode temp = head;
//找到链表最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = doubleNode;
doubleNode.pre = temp;
}
//删除节点
public void delete(int data) {
DoubleNode temp = head.next;
boolean flag = false; //标志是否找到待删除节点的前一个节点
while (true) {
if (temp == null) {
//已经遍历到链表最后了
break;
} else if (temp.data == data) {
//找到待删除节点
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.pre.next = temp.next;
if (temp.next != null) {
//若删除节点不为最后一个节点
temp.next.pre = temp.pre;
}
} else {
System.out.println("要删除的节点不存在");
}
}
//输出链表
public void show() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
DoubleNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
}
总结
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注编程网的更多内容!