亲宝软件园·资讯

展开

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

去吧猫头夜鹰 人气:0
想了解java数据结构基础:单链表与双向链表的相关内容吗,去吧猫头夜鹰在本文为您仔细讲解数据结构单链表与双向链表基础的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:java基础,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 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;
		}
	}
}

总结

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

加载全部内容

相关教程
猜你喜欢
用户评论