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;
		}
	}
}

总结

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

(0)

相关推荐

  • Java如何实现单链表的增删改查

    一.新建学生节点类 Stu_Node节点包含: 学号:int num; 姓名:String name; 性别:String gender; 下一个节点:Stu_Node next; 为了便于打印节点内容需要重写toString方法 class Stu_Node{ int num; String name; String gender; Stu_Node next; @Override public String toString() { return "Stu_Node{" + &qu

  • java实现单链表、双向链表

    本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {

  • Java数据结构之链表实现(单向、双向链表及链表反转)

    前言 之前学习的顺序表查询非常快,时间复杂度为O(1),但是增删改效率非常低,因为每一次增删改都会元素的移动.可以使用另一种存储方式-链式存储结构. 链表是一种物理存储单元上非连续.非顺序的存储结构.链表由一序列的结点(链表中的每一个元素成为结点)组成. 结点API设计: 类名 Node 构造方法 Node(T t,Node next) 创建Node对象 成员变量 T item:存储数据 Node next :指向下一个结点 结点类: public class Node<T>{ Node ne

  • Java单链表反转图文教程

    前言 最近在回顾链表反转问题中,突然有一些新的发现和收获,特此整理一下,与大家分享

  • Java双向链表按照顺序添加节点的方法实例

    分析过程: 首先需要比较待添加的节点编号与已有的节点编号的大小,若待添加的节点编号已经存在,则不能加入.为防止出现空指针的情况,需要对节点的位置进行判断. 示例代码: package linkedlist; public class DoubleLinkedListDemo { public static void main(String[] args) { // 测试 System.out.println("双向链表的测试"); // 创建节点 Node node1 = new No

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

    目录 单链表: 实现思路: 代码实现: 双向链表: 实现思路: 代码实现: 总结 单链表: 每个数据是以节点的形式存在的 每个节点分为数据域和指针域 数据域中保存该节点的数据 指针域中保存指向下一个节点的指针 实现思路: 节点类SingleNode中保存数据和指向下一个节点的指针 单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法 对于链表方法,涉及到位置查找,如在指定位置增加.删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置. 对于节点的增加

  • Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • Java数据结构之单链表的实现与面试题汇总

    目录 1 单链表 1.1 单链表介绍 1.2 单链表的实现思路分析 1.3 实现代码 2 单链表的面试题 2.1 统计单链表中有效节点数量 2.2 新浪–倒数第k个节点 2.3 腾讯–单链表的反转 2.4 百度–逆序打印单链表 1 单链表 1.1 单链表介绍 由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表.单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻.

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

    目录 单向链表 单链表图解 代码 双向链表 编码 总结 单向链表 单向链表比顺序结构的线性表最大的好处就是不用保证存放的位置,它只需要用指针去指向下一个元素就能搞定. 单链表图解 图画的比较粗糙,简单的讲解一下: 上面四个长方形,每个长方形都是一个节点.在长方形中,一种包含两个东西,一个是当前节点的元素,一个是指向下一节点的地址.这个下一个节点的地址指向了下一个节点中的元素.以此类推. 在最左边的叫做头节点,同样,最后面的叫尾节点. 所以,我们所有的操作都是根据节点来进行操作. 代码 这些代码都

  • C#数据结构之单链表(LinkList)实例详解

    本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data

  • python算法与数据结构之单链表的实现代码

    =一.链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是

  • java实现简单单链表

    本文实例为大家分享了java实现简单单链表的具体代码,供大家参考,具体内容如下 一.定义: 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(相当于JAVA中的引用,指示后继元素存储位置,),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 二.结构: 如图所示,data就是当前节点的数据,next是指针,指针存放的是内存地址,是当前结点的下一结点内存地址,顺着这个地址就能找

  • C语言数据结构之单链表与双链表的增删改查操作实现

    目录 前言 单链表的增删改查 定义结构体以及初始化 增加结点 删除结点 查找修改结点 移除结点 最终效果 双链表的基本操作 初始化建表 遍历双链表 指定位置插入结点 指定位置删除结点 查找结点位置 最终效果 结语 前言 上篇博客分享了创建链表传入二级指针的细节,那么今天就分享几个c语言课程实践设计吧.这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了,那么再应对复杂的链表类的题也就能慢慢钻研了.学习是一个积累的过程,想要游刃有余就得勤学苦练! 单链表的增删改查 (1)项目需求 构造带有头结点的

  • Java数据结构之环形链表和约瑟夫问题详解

    目录 一.环形链表 1.创建结点 2.添加小结点 3.显示循环链表 二.约瑟夫问题 1.问题描述 2.首先确定圈大小及开始位置 3.出圈操作 4.出圈方法完整代码 总结 一.环形链表 1.创建结点 环形链表其实也很好理解,就是将单链表的头和尾连接起来,就形成了环形链表. public class Node { public int data; public Node next; public Node(int data) { this.data = data; } @Override publi

随机推荐