链表是一种重要的数据结构,在程序设计中占有很重要的地位。链表包括单向链表,双向链表和循环链表。Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。
class Node (双向链表)
{
Object data;
Node previous;//指向上一个结点
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类,任何类对象都可以给其赋值,增加了代码的通用性。为了使链表可以被访问还需要定义一个表头,表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点,还可以增加一指向链表尾部的指针,另外还可以用一个域来表示链表的大小,当调用者想得到链表的大小时,不必遍历整个链表。
链表的数据结构:
我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧,Pointer并非存储指向当前结点的指针,而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢?这是因为当删除当前结点后仍需保证剩下的结点构成链表,如果Pointer指向当前结点,则会给操作带来很大困难。那么如何得到当前结点呢,我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作,通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点,并使其成为当前结点。remove()方法删除当前结点同时返回其内容,并使其后继结点成为当前结点,如果删除的是最后一个结点,则第一个结点变为当前结点。
链表类List的源代码如下:
import java.io.*;
public class List
{
/*用变量来实现表头*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整个链表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*链表复位,使第一个结点成为当前结点*/
{
Pointer=null;
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0);
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回当前结点的下一个结点的值,并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在当前结点前插入一个结点,并使其成为当前结点*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length++;
}
public int size()
/*返回链表的大小*/
{
return (Length);
}
public Object remove()
/*将当前结点移出链表,下一个结点成为当前结点,如果移出的结点是最后一个结点,则第一个结点成为当前结点*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
练习:
package Link;
/**
* 节点接口
*
* 要求:
* 1.实现下边所有的方法
* 2.根据链表中存储的数据进行排序(比如学生根据学分)
* 3.单链表、双链表、循环链表都实现一遍
* 4.链表总结
*/
public interface NodeLinkedListInterface {
/**
* 添加节点的方法
*
* @param node新添加的节点对象
*/
public abstract void add(Node node);
/**
* 在指定索引位置添加新节点
* @param node要添加的新节点
* @param index指定的索引位置
*/
public abstract void add(Node node, int index);
/**
* 移除指定的节点
* @param node要被移除的节点对象
* @return 返回true和false,true表示移除成功,false表示移除失败
*/
public abstract boolean remove(Node node);
/**
* 移除指定所以位置的节点
* @param index指定要移除的节点索引
* @return 返回true和false,true表示移除成功,false表示移除失败
*/
public abstract boolean remove(int index);
/**
* 获取指定索引位置的节点对象
*
* @param index指定的索引位置
* @return 返回节点对象,如果index的范围超出size,则返回null.
*/
public abstract Node get(int index);
/**
* 获取双链表中存储的元素总数
*
* @return 返回size的值,如果为0则表示链表中没有节点
*/
public abstract int size();
}
package Link;
public class NodeLinkedList
implements NodeLinkedListInterface {//接口
private int size=0;//节点总数
private Node root=null;//根节点
private Node last=null;//尾节点
@Override
public void add(Node node) {
if(null==root){
//让根节点和尾节点都指向新添加的节点
root=node;
last=node;
}else{
//向尾节点添加节点
last.setNext(node);
//将设为上一个节点
node.setPrevious(last);
last=node;
}
size++;
}
@Override
public void add(Node node, int index) {
if(size<index||index<0){
System.out.println("下标越界");
}else{
Node newnode=get(index);
if(index==0){
//如果链表没有结点
root=node;
}else{
//得到上一个结点
Node pnode=newnode.getPrevious();
//设置新的引用关系
pnode.setNext(node);
node.setPrevious(pnode);
}
//设置新的引用关系
node.setNext(newnode);
newnode.setPrevious(node);
}
size++;
}
@Override
public Node get(int index) {
//超出索引,返回null
if(index>=size||index<0){
return null;
}
//让node为根节点
Node node=root;
//遍历至索引位置
for(int i=0;i<index;i++){
//获取node节点的下一个
node=node.getNext();
}
return node;
}
@Override
public boolean remove(Node node) {
int I =0;
for(int i=0;i<size;i++){
Node nodenow = get(i);
if(nodenow==node){
I = i;
}
}
//得到当前索引位置的节点
Node nodenow = get(I);
//得到父节点
Node Fnode = nodenow.getPrevious();
//得到子节点
Node Cnode = nodenow.getNext();
if(Fnode==null){
root=Cnode;
}else if(Cnode==null){
Fnode.setNext(null);
}else{
Fnode.setNext(Cnode);
Cnode.setPrevious(Fnode);
}
size--;
return true;
}
@Override
public boolean remove(int index) {
if(index<0||index>=size){
return false;
}else{
//得到当前索引位置的结点
Node node=get(index);
//得到上一个结点
Node pnode=node.getPrevious();
//得到下一个结点
Node nnode=node.getNext();
if(pnode==null){
root=nnode;
}else if(nnode==null){
pnode.setNext(null);
}else{
pnode.setNext(nnode);
nnode.setPrevious(pnode);
}
size--;
return true;
}
}
@Override
public int size() {
return size;
}
}
package Link;
/**
* 节点类
* @author Sara
*
*/
public class Node {
//节点数据
private int data;
private Node next;
private Node previous;
public Node(){
}
public Node(int data){
this.data=data;
}
public Node(int data,Node next,Node previous){
this.data=data;
this.next=next;
this.previous=previous;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
}
package Link;
import java.util.Random;
public class Manager {
/**
* @param args
*/
public static void main(String[] args) {
NodeLinkedListInterface nll = new NodeLinkedList();
Random rand = new Random();
for(int i=0;i<10;i++){
Node node = new Node(rand.nextInt(100));
nll.add(node);
}
Node node = new Node(89);
nll.add(node, 5);
for(int i=0;i<nll.size();i++){
if(i==5){
Node node1 = nll.get(i);
System.out.print("new "+node1.getData()+" ");
}else
{
Node node1 = nll.get(i);
System.out.print(node1.getData()+" ");
}
}
System.out.println(" ");
nll.remove(6);
for(int i=0;i<nll.size();i++){
if(i==6){
Node node1 = nll.get(i);
System.out.print("该处删除"+" "+node1.getData()+" ");
}else
{
Node node1 = nll.get(i);
System.out.print(node1.getData()+" ");
}
}
System.out.println(" ");
System.out.println("移除的是第" + (6) + "个节点");
nll.remove(nll.get(5));
for (int i = 0; i < nll.size(); i++) {
Node node2 = nll.get(i);
System.out.print(node2.getData() + " ");
}
for (int i = 1; i < nll.size(); i++) {
for (int j = i; j > 0; j--) {
if (nll.get(j).getData() < nll.get(j - 1).getData()) {
int temp = nll.get(j).getData();
nll.get(j).setData(nll.get(j - 1).getData());
nll.get(j - 1).setData(temp);
}
}
}
System.out.println("");
System.out.println("从小到大排序后的结果为:");
for (int k = 0; k < nll.size(); k++) {
Node nodex = nll.get(k);
System.out.print(nodex.getData()+" ");
}
}
}
分享到:
相关推荐
链表实现集合运算 链表实现集合交并差运算
数据结构 课程设计 用链表实现集合并集 c++
c++,算法链表实现一元多项式相加,通过链表实现,非常好的一个程序
大学期间用C语言链表实现的一个图书管理系统,主要功能有 a. 设备申请。由专业人员填写“申请表”送交领导批准购买。 b. 设备入库。新设备购入后要立即进行设备登记(包括类别、设备名、型号、规格、单价、数量、...
栈的实现(C语言)数组实现以及链表实现源码,以及各个功能测试代码函数等 和后缀式转前缀式的用例
(1) 利用链表实现长整数的存储,每个节点含一个整型变量; (2) 整型变量的范围:-(2^15 -1)~(2^15 -1); (3) 输入与输出形式每四位一组,组间用逗号分隔开。如:1986,8213,1935,2736,3299; (4) 界面...
用链表实现线性表java用链表实现线性表
链表 实现 c++ cpp 数据结构 作业 链表 实现 c++ cpp 数据结构 作业
用链表实现多级菜单,STM32彩屏显示多级菜单
用C语言链表实现进程转换,阻塞变就绪,就绪变执行,执行变阻塞三种状态的转换
用链表实现栈和队列的操作,使链表操作更加成熟,熟练栈和队列的机制
用链表实现的职工管理软件 ( C+ + )
基于C语言的超市商品管理系统链表实现实验报告.pdf
小型通讯录程序c语言链表实现(源代码) CentOS下vim编辑器gcc编译器
通讯录管理系统数据结构C语言版链表实现实验报告.doc
内容概要:学生成绩管理系统的课设报告,报告包括程序由C语言链表实现,包含界面菜单,密码登录,录入、增加、删除、修改、显示、保存、读取学生信息,查询单科成绩排名,查询学生成绩,查询不及格超过2科学生的名单...
数据结构实验报告-利用链表实现简易学生信息管理系统,内容包含实验目的,实验环境,实验源代码,实验运行截图,实验小结等。 说明:如有bug,还请反馈!
C语言利用链表实现单词本管理
JAVA链表实现类(数据结构学习).chm
python利用数组和链表实现栈和队列 数组和链表.pdf