java数据结构基础:单链表与双向链表

java数据结构基础:单链表与双向链表

目录单链表：实现思路：代码实现：双向链表：实现思路：代码实现：总结

单链表：

每个数据是以节点的形式存在的

每个节点分为数据域和指针域

数据域中保存该节点的数据

指针域中保存指向下一个节点的指针

实现思路：

节点类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 voidhttp:// show() {

//判断链表是否为空

if (head.next == null) {

System.out.println("链表为空");

return;

}

http:// 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 + '}';

}

}

双dPjQiaQhQr向链表类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;

}

//删除节点dPjQiaQhQr

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;

}

}

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。