java 实现双向链表实例详解

java 实现双向链表实例详解

双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力。话不多说,上代码:

    首先是链表的节点类:

/**
 * 链表节点
 * @author Administrator
 *
 * @param <T>
 */
public class ChainNode<T> {
 private T data;
 //对象编号
 private int dataNo; 

 public ChainNode<T> nextChainNode;
 public ChainNode<T> preChainNode;
 public ChainNode(T data, ChainNode<T> nextChainNode,
   ChainNode<T> preChainNode) {
  this.data = data;
  this.nextChainNode = nextChainNode;
  this.preChainNode = preChainNode;
 } 

 public ChainNode(T data) {
  this.data = data;
 } 

 public int getDataNo() {
  return dataNo;
 } 

 public void setDataNo(int dataNo) {
  this.dataNo = dataNo;
 } 

 public void setData(T data) {
  this.data = data;
 } 

 public T getData() {
  return data;
 } 

}

 然后是链表:

<pre name="code" class="java">/**
 * 链表实现类
 * @author Administrator
 *
 * @param <T>
 */
public class Chain<T> {
 //头节点
 private ChainNode<T> headNode;
 //末尾节点指针
 private ChainNode<T> lastNode;
 private int size; 

 //创建链表就创建头节点
 public Chain() {
  this.headNode = new ChainNode<T>(null);
  this.lastNode = headNode; 

 }
 //增加一个节点
 public void addNode(T data) {
  ChainNode<T> node = new ChainNode<T>(data);
  if(lastNode != null){
   lastNode.nextChainNode = node;
   node.preChainNode = node;
   node.setDataNo(size);
   lastNode = node;
   size++;
  }
 }
 //删除指定索引的节点
 public void deleteNode(int dataNo) throws Exception {
  if(getSize() == 0){
   throw new Exception("chain is empty");
  }
  for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) {
   if(node.getDataNo() == dataNo){
    node.preChainNode.nextChainNode = node.nextChainNode;
    if(node.nextChainNode != null){
     node.nextChainNode.preChainNode = node.preChainNode;
    } 

    node.nextChainNode = null;
    node.preChainNode = null;
    size--;
    //重新设置节点的编号
    for (ChainNode<T> chainNode = node.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {
     chainNode.setDataNo(chainNode.getDataNo()-1);
    }
    return; 

   }
  }
  throw new Exception("the corresponding data that can not be found");
 }
 //获取指定索引的节点
 public T get(int dataNo) throws Exception {
  if(getSize() == 0){
   throw new Exception("chain is empty");
  }
  for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) {
   if(node.getDataNo() == dataNo){
    return node.getData();
   }
  }
  throw new Exception("the corresponding data that can not be found");
 }
 //修改对应索引的节点
 public void set(int dataNo,T data) throws Exception {
  if(getSize() == 0){
   throw new Exception("chain is empty");
  }
  for (ChainNode<T> node = headNode.nextChainNode;node != null;node = node.nextChainNode) {
   if(node.getDataNo() == dataNo){
    node.setData(data);
    return;
   }
  }
  throw new Exception("the data that is to be modified can not be found");
 }
 //是否包含对应数据的节点
 public boolean isContains(T data) throws Exception {
  if(getSize() == 0){
   throw new Exception("chain is empty");
  }
  for (ChainNode<T> chainNode = headNode.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {
   if(chainNode.getData() == data){
    return true;
   }
  } 

  return false;
 }
 //获取节点数量(不含头节点)
 public int getSize() {
  return size;
 }
}

测试一下:

public class ChainTest {
 public static void main(String[] args) throws Exception{
  String oneString = "one";
  String twoString = "two";
  String threeString = "three";
  String fourString = "four";
  Chain<String> chain = new Chain<String>();
  chain.addNode(oneString);
  chain.addNode(twoString);
  chain.addNode(threeString);
  chain.addNode(fourString);
  for (int i = 0; i < chain.getSize(); i++) {
   String string2 = chain.get(i);
   System.out.println(string2);
  }
  try {
   String string = chain.get(2);
   System.out.println("the data of the second node is"+string);
   System.out.println(chain.isContains(fourString));
   chain.set(1, "haha");
   System.out.println("modify chain");
   for (int i = 0; i < chain.getSize(); i++) {
    String string2 = chain.get(i);
    System.out.println(string2);
   } 

   chain.deleteNode(3);
   System.out.println("delete one node");
   for (int i = 0; i < chain.getSize(); i++) {
    String string2 = chain.get(i);
    System.out.println(string2);
   }
  } catch (Exception e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
 }
}

结果:

one
two
three
four
the data of the second node isthree
true
modify chain
one
haha
three
four
delete one node
one
haha
three

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • JAVA实现链表面试题

    这份笔记整理了整整一个星期,每一行代码都是自己默写完成,并测试运行成功,同时也回顾了一下<剑指offer>这本书中和链表有关的讲解,希望对笔试和面试有所帮助. 本文包含链表的以下内容: 1.单链表的创建和遍历 2.求单链表中节点的个数 3.查找单链表中的倒数第k个结点(剑指offer,题15) 4.查找单链表中的中间结点 5.合并两个有序的单链表,合并之后的链表依然有序[出现频率高](剑指offer,题17) 6.单链表的反转[出现频率最高](剑指offer,题16) 7.从尾到头打印单链表(

  • java 中链表的定义与使用方法

    java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • Java中双向链表详解及实例

    Java中双向链表详解及实例 写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin

  • Java 数据结构链表操作实现代码

    链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个链

  • Java 链表的定义与简单实例

     Java 链表的定义与简单实例 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new mytype("

  • JAVA 数据结构链表操作循环链表

    JAVA 链表操作:循环链表 主要分析示例: 一.单链表循环链表 二.双链表循环链表 其中单链表节点和双链表节点类和接口ICommOperate<T>与上篇一致,这里不在赘述.参考:JAVA链表操作:单链表和双链表http://www.jb51.net/article/95113.htm 一.单链表循环链表 package LinkListTest; import java.util.HashMap; import java.util.Map; public class SingleCycle

  • Java单链表基本操作的实现

    最近被问到链表,是一个朋友和我讨论Java的时候说的.说实话,我学习编程的近一年时间里,学到的东西还是挺少的.语言是学了Java和C#,关于Web的学了一点Html+css+javascript.因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究.但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧. 但是我还是抽了一个晚上加半天的时间看了一下单向链表.并且使用Java试着写了一个实例出来.没有接触过链表的朋友可以作为参考,希望大家多提宝贵

  • java 实现双向链表实例详解

    java 实现双向链表实例详解 双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力.话不多说,上代码:     首先是链表的节点类: /** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainN

  • Java多线程ForkJoinPool实例详解

    引言 java 7提供了另外一个很有用的线程池框架,Fork/Join框架 理论 Fork/Join框架主要有以下两个类组成. * ForkJoinPool 这个类实现了ExecutorService接口和工作窃取算法(Work-Stealing Algorithm).它管理工作者线程,并提供任务的状态信息,以及任务的执行信息 * ForkJoinTask 这个类是一个将在ForkJoinPool执行的任务的基类. Fork/Join框架提供了在一个任务里执行fork()和join()操作的机制

  • java 抽象类的实例详解

    java 抽象类的实例详解 前言: 什么是抽象类?这名字听着就挺抽象的,第一次听到这个名字还真有可能被唬住.但是,就像老人家所说的,一切反动派都是纸老虎,一切有着装x名字的概念也是纸老虎.好吧,我们已经从战略上做到了藐视它,现在就要战术上重视它,如同要解决纸老虎,就要一个牙齿一个牙齿地敲,一个爪子一个爪子地拔:解决这种抽象概念也一样,先要把它具体化,细分化,然后一个一个地来. 我一般遇到新的概念都会问三个问题: 1.这个东西有什么用?用来干什么的?它的意义在哪里?(显然,如果是没用的东西,就没必

  • Java 多线程优先级实例详解

    Java 多线程优先级实例详解 线程的优先级将该线程的重要性传递给调度器.尽管CPU处理现有线程集的顺序是不确定的,但是调度器将倾向于让优先权最高的线程先执行. 你可以用getPriority()来读取现有线程的优先级,并且在任何时刻都可以通过setPriority()来修改优先级. import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; public class SimplePrio

  • java LinkedList的实例详解

    java LinkedList的实例详解 站在Java的角度看,玩队列不就是玩对象引用对象嘛! 实例代码: public class LinkedList<E> implements List<E>, Deque<E> { Node<E> first; Node<E> last; int size; public boolean add(E e) { final Node<E> l = last; final Node<E>

  • Java 反射机制实例详解

    Java 反射机制实例详解 一.JAVA是动态语言吗? 一般而言,说到动态言,都是指在程序运行时允许改变程序结构或者变量类型,从这个观点看,Java和C++一样,都不是动态语言. 但JAVA它却有着一个非常突出的动态相关机制:反射.通过反射,Java可以于运行时加载.探知和使用编译期间完全求和的类.生成其对象实体,调用其方法或者对属性设值.所以Java算是一个半动态的语言吧. 反射的概念: 在Java中的反射机制是指在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法; 对于任意一个对

  • java回调机制实例详解

    java回调机制实例详解 以前不理解什么叫回调,天天听人家说加一个回调方法啥的,心里想我草,什么叫回调方法啊?然后自己就在网上找啊找啊找,找了很多也不是很明白,现在知道了,所谓回调:就是A类中调用B类中的某个方法C,然后B类中反过来调用A类中的方法D,D这个方法就叫回调方法,这样子说你是不是有点晕晕的,其实我刚开始也是这样不理解,看了人家说比较经典的回调方式: Class A实现接口CallBack callback--背景1 class A中包含一个class B的引用b --背景2 clas

  • Java 比较字符串实例详解

     Java 比较字符串实例详解 公司让实现一个自动清除1小时内数据,SQL不熟悉,无奈之下,只能本地DB存储当前时间+小时去和当前时间进行比对.折腾好半天,突然想到Java提供了一个方法,也是进行字符串比较的,傻眼了.一起来看看吧~ CompareTo()方法简介 首先,它属于java.lang.String包下,是Java提供的一个字符串比较的方法,详情介绍如下: CompareTo()返回值: int 返回值类型分别有三种,小于0,等于0,大于0 1. 如果字符串相等返回值0: 2. 如果第

  • java 归并排序的实例详解

    java 归并排序的实例详解 归并排序 归并排序,指的是将两个已经排序的序列合并成一个序列的操作. 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 Java代码 /** * 归并排序 * * @param ts */ @SuppressWa

  • java 内部类的实例详解

    java 内部类的实例详解 可以将一个类的定义放在另一个类的定义内部,这就是内部类. 内部类是一个非常有用的特性但又比较难理解使用的特性(鄙人到现在都没有怎么使用过内部类,对内部类也只是略知一二). 第一次见面 内部类我们从外面看是非常容易理解的,无非就是在一个类的内部在定义一个类. public class OuterClass { private String name ; private int age; public String getName() { return name; } p

随机推荐