`
何以-追梦
  • 浏览: 3239 次
  • 性别: Icon_minigender_1
  • 来自: 南京
最近访客 更多访客>>
社区版块
存档分类
最新评论

双向链表

阅读更多

       今天我想跟大家来唠叨一下双向链表,何为双向链表?简而言之,每个结点存储两个链,并允许双向遍历的链表称为双向链表。我对于链表的理解是这样的,一个结点类,一个位置类,一个链表本身类。

一、结点类

public class DoubleLinkNode {
	public String iData;
	//前一个结点
	public DoubleLinkNode prev;
	//后一个结点
	public DoubleLinkNode next;
	
	public DoubleLinkNode(String iData){
		this(iData,null,null);
	}

	public DoubleLinkNode(String iData, DoubleLinkNode dln, DoubleLinkNode dln2) {
		this.iData=iData;
		this.prev=dln;
		this.next=dln2;
	}
	
}

 这个类比较简单,没什么好说,对于第二个构造器,主要是为了使后面结点之间的连接更简洁。你也可以不用这个构造器。

二、位置类(迭代器类)

public class DbLinkListIterator {
	//标识当前的位置
	DoubleLinkNode current;
	DbLinkListIterator(DoubleLinkNode dln) {
		current=dln;
	}
	//判断当前位置是否有效
	public boolean isValid(){
		return current!=null;
	}
	//向前行进
	public void advace(){
		if (isValid()) {
			current=current.next;
		}
	}
	//向后倒退
	public void back(){
		if (isValid()) {
			current=current.prev;
		}
	}
	//返回当前位置的标识符
	public String retrieve(){
		if (isValid()) {
			return current.iData;
		}
		return null;
	}
}

 这个类主要用来反馈链表当前的位置,如果你不想单独建这个类,你可以把它放在链表本身类的内部。但是本人觉得把它单独抽象出来成一个类,结构会更加的清晰。

三、链表本身类

public class LinkList_Double {
	//头结点
	private DoubleLinkNode header;
	//尾结点
	private DoubleLinkNode tail;
	//初始化头尾结点
	public LinkList_Double() {
		header=new DoubleLinkNode("header");
		tail=new DoubleLinkNode("tail",header,null);
		header.next=tail;
	}
	//判断双向链表是否为空
	public boolean isEmpty(){
		return header.next==tail||tail.prev==header;
	}
	//第一个结点之前的位置
	public DbLinkListIterator zero(){
		return new DbLinkListIterator(header);
	}
	//第一个结点的位置
	public DbLinkListIterator first(){
		if (!isEmpty()) {
			return new DbLinkListIterator(header.next);
		}
		return new DbLinkListIterator(header);
	}
	//最后一个结点的位置
	public DbLinkListIterator last(){
		if (!isEmpty()) {
			return new DbLinkListIterator(tail.prev);
		}
		return new DbLinkListIterator(tail);
	}
	//指定位置之后插入方法
	public void insertAfter(String obj,DbLinkListIterator pos){
		if (pos!=null&&pos.current!=null) {
			DoubleLinkNode newDoubleLinkNode=new DoubleLinkNode(obj,pos.current,pos.current.next);
			newDoubleLinkNode.prev.next=newDoubleLinkNode;
			newDoubleLinkNode.next.prev=newDoubleLinkNode;
		}
	}
	
	//指定位置之前插入方法
	public void insertBefore(String obj,DbLinkListIterator pos){
		if (pos.current!=header&&pos!=null&&pos.current!=null) {
			DoubleLinkNode newDoubleLinkNode=new DoubleLinkNode(obj,pos.current.prev,pos.current);
			newDoubleLinkNode.prev.next=newDoubleLinkNode;
			newDoubleLinkNode.next.prev=newDoubleLinkNode;
		}
	}
	
	//查找方法
	public DbLinkListIterator find(String key){
		DoubleLinkNode itr=header.next;
		while (itr!=null) {
			if (itr.iData.equals(key)) {
				return new DbLinkListIterator(itr);
			}
			itr=itr.next;
		}
		return null;
	}
	//删除方法
	public void delete(String key){
		DbLinkListIterator itr=find(key);
		if (itr==null) {
			System.out.println("不存在该关键字");
			return;
		}
			itr.current.prev.next=itr.current.next;
			itr.current.next.prev=itr.current.prev;
	}
	
	//向前显示
	public void displayBofore(){
		if (isEmpty()) {
			System.out.println("该双向链表为空");
		}else {
			DbLinkListIterator itr=first();
			while (itr!=null&&!itr.retrieve().equals("tail")) {
				System.out.print(itr.retrieve()+" ");
				itr.advace();
			}
		}
	}
	
	//向后显示
	public void displayAfter(){
		if (isEmpty()) {
			System.out.println("该双向链表为空");
		}else {
			DbLinkListIterator itr=last();
			while (itr!=null&&!itr.retrieve().equals("header")) {
				System.out.print(itr.retrieve()+" ");
				itr.back();
			}
		}
	}
}

为了方便,作者的想法是虚构两个结点,即头结点、尾结点,这样做的好处就是能够保证每次插入有效结点时,它的前后都有结点,这样就少了许多的条件判断。当然双向链表本身的方法肯定不止这么一点,我只是大概的列举了一些。

四、测试类

public class LinkList_doubleTest {
	public static void main(String[] args) {
		LinkList_Double linkList_Double=new LinkList_Double();
		//插入第一个结点
		linkList_Double.insertAfter("a", linkList_Double.zero());
		//在指定结点之后插入
		linkList_Double.insertAfter("b", linkList_Double.find("a"));
		linkList_Double.insertAfter("c", linkList_Double.find("b"));
		
		//在指定结点之前插入
		linkList_Double.insertBefore("e", linkList_Double.find("b"));
		linkList_Double.insertBefore("f", linkList_Double.first());
		//删除指定结点
		linkList_Double.delete("f");
		//顺序显示
		linkList_Double.displayBofore();
		//逆序显示
		linkList_Double.displayAfter();
	}
}

 最后,作者也是正在学习的过程中,自然还有很多 考虑不周全的地方,如有,还请见谅,并希望您能指出我的不足之处,大家一起学习、进步。

2
1
分享到:
评论

相关推荐

    支持类模版的C++双向链表

    在C++编程中,双向链表是一种非常重要的数据结构,它允许在列表的任一位置进行插入和删除操作,而不必像数组那样依赖于索引。在这个“支持类模版的C++双向链表”中,我们将探讨如何利用C++的模板特性来实现一个灵活...

    Linux内核双向链表简单分析

    ### Linux内核双向链表简单分析 #### 链表数据结构简介 链表作为一种基本且重要的数据结构,在操作系统及各种软件系统中扮演着至关重要的角色。尤其在Linux内核中,链表更是广泛应用于内存管理、进程调度、文件...

    双向链表双向链表双向链表

    双向链表是一种高级数据结构,它在计算机科学中被广泛应用于各种算法和程序设计中。与单链表相比,双向链表的主要特点是每个节点不仅包含指向下一个节点的指针,还包含一个指向前一个节点的指针。这种设计使得双向...

    C++双向链表统计文章单词出现频率

    在这个特定的项目中,“C++双向链表统计文章单词出现频率”是一个涉及数据结构和算法的应用,目标是实现一个程序来分析文本文件,计算并显示文章中每个单词出现的次数。双向链表作为数据结构的核心,其特点是每个...

    双向链表的操作

    双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...

    java 单链表和双向链表的实现

    本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现,以及相关的操作,如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先,我们来理解单链表和双向链表的基本概念。单链表是一种线性...

    创建双向链表_双向链表_

    双向链表是一种特殊类型的数据结构,与常见的单向链表相比,它具有更丰富的操作能力,可以支持前后两个方向的遍历。本篇文章将深入探讨如何创建双向链表以及其在增加和删除操作中的应用。 双向链表的每个节点不仅...

    操作系统课设-线程安全的双向链表

    操作系统课程设计中实现线程安全的双向链表是一项重要的实践任务,这涉及到多线程编程、数据结构以及并发控制等核心知识点。在这个项目中,我们主要关注如何在多线程环境下构建一个能够正确操作(如插入、删除)而不...

    双向链表的增删改查

    双向链表(Double Linked List)是链表的一种变体,它允许我们在列表中的每个节点处进行前向和后向的遍历。本文将详细探讨如何实现双向链表的增、删、改、查操作,并通过C++编程语言的DLink.cpp文件进行实际应用。 ...

    数据结构-双向链表

    双向链表是一种特殊的数据结构,它在编程中具有重要的应用。本文将深入探讨双向链表的概念,实现,以及如何进行基本操作。 双向链表,顾名思义,是一种链式存储结构,其中每个节点包含两个指针,一个指向前一个节点...

    stm32f103 双向链表

    在这个项目中,我们讨论的是如何在STM32F103上实现一个双向链表的数据结构。双向链表是一种特殊的数据结构,它允许我们在列表中的节点之间进行前向和后向的移动,这在处理动态数据集合时非常有用。 首先,我们要...

    用双向链表做的n的阶乘

    在编程领域,双向链表是一种数据结构,它允许在列表中的元素之间进行前向和后向的导航。这种数据结构在处理需要频繁插入、删除或遍历操作的问题时特别有用。而“n的阶乘”是数学概念,表示1到n的所有整数的乘积,记...

    数据结构源代码之双向链表

    ### 数据结构源代码之双向链表 #### 概述 本文档主要介绍如何通过C语言实现双向链表的基本操作。继单链表之后,双向链表作为一种更灵活的数据结构,支持从前向后以及从后向前的遍历。双向链表在每个节点中除了包含...

    数据结构 双向链表(C++)

    双向链表是一种特殊的数据结构,它在计算机程序设计中扮演着重要角色,特别是在C++这样的编程语言中。本节将深入探讨双向链表的概念、其结构、操作以及C++中的实现。 双向链表与单链表不同,它允许每个节点不仅有一...

    大数阶乘 双向链表

    本主题聚焦于如何使用双向链表这一数据结构来实现大数阶乘的计算。双向链表允许我们有效地存储和操作大数,同时保持良好的性能。 首先,我们需要了解双向链表的基本概念。双向链表是一种线性数据结构,其中每个节点...

    双向链表实现结点类

    定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...

    C++经典算法 双向链表

    ### C++经典算法:双向链表 在计算机科学领域中,数据结构是极其重要的基础知识之一。其中链表作为一种常见的线性表实现方式,在各种应用场景中都有广泛的应用。本篇文章将根据给定的代码片段深入探讨双向链表的...

    双向链表模板类简单实现

    本文将深入探讨双向链表及其在C++中的模板类实现,以"双向链表模板类简单实现"为主题,我们来详细了解一下这个话题。 双向链表,与单向链表不同,它的每个节点不仅包含数据,还包含两个指针,一个指向下一个节点...

    C语言编写的双向链表

    双向链表是链表的一种变体,它在每个节点中不仅存储了数据,还包含了指向前后节点的指针,这使得在链表中的导航变得更加灵活。 双向链表的结构: 在C语言中,一个双向链表的节点通常包含三个部分:数据域,以及两个...

    双向链表.cpp 双向链表类定义及测试代码 c++

    双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材

Global site tag (gtag.js) - Google Analytics