Java实现线性表的链式存储

本文实例为大家分享了Java实现线性表的链式存储,供大家参考,具体内容如下

链表:一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

package algorithm.datastructure.linklist;
import java.util.NoSuchElementException;

/*
* 链表
* 物理存储上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现
*
* */
public class LinkedList {
 private Node head;//头节点
 private int size;//链表长度
 static private class Node{
  private int data;
  private Node next;
  public Node(){

  }
  private Node(int data,Node next){
   this.data=data;
   this.next=next;
  }
 }

 //初始化空链表
 public LinkedList(){
  //head=null;
 }

 //添加元素
 public Boolean add(int element){
  linkLast(element);
  return true;
 }
 //在某个位置之前添加元素
 public Boolean add(int index,Integer element){
  checkPositionIndex(index);
  if (index==size){
   linkLast(element);
  } else {
   linkBefore(element,node(index));
  }

  return true;
 }
 //根据下标获取元素
 public int get(int index){
  checkElementIndex(index);
  return node(index).data;
 }
 //获取第一个元素
 public Integer getFirst(){
  Node f=head;
  if (f==null){
   throw new NoSuchElementException();
  } else {
   return f.data;
  }
 }
 //获取最后一个元素
 public Integer getLast(){
  if (size==0){
   throw new NoSuchElementException();
  }
  int index=size-1;
  return node(index).data;
 }

 //删除第一个元素
 public Integer removeFirst(){
  Node f=head;
  if (f==null){
   throw new NoSuchElementException();
  } else {
   return unlink(head);
  }
 }

 //删除最后一个元素
 public Integer removeLast(){
  if (size==0){
   throw new NoSuchElementException();
  }
  int index=size-1;
  return unlink(node(index));
 }

 //根据索引删除元素
 public Integer remove(int index){
  checkElementIndex(index);
  return unlink(node(index));
 }

 //销毁链表
 public void destroyList(){
  clearList();
 }
 //将链表置为空表
 public void clearList() {

  for (Node p=head;p!=null;){
   Node next=p.next;//记录下一个结点
   p=null;//删除当前结点
   p=next;//指向下一个结点
  }
  size=0;
  head=null;
 }
 //遍历链表
 public void traverseList(){

  for (Node p=head;p!=null;){
   System.out.println(p.data);
   p=p.next;
  }
 }

 //返回链表元素个数
 public int size(){
  return size;
 }

 //尾部添加结点
 private void linkLast(int element){
  Node cur =null,p;
  if (size==0){//没有结点时
   head=new Node(element,null);
   size++;
   return;
  }
  for (p=head;p!=null;){//有结点时候
   cur=p;
   p=cur.next;
  }
  cur.next= new Node(element,null);//尾部添加元素
  size++;
 }

 //在某结点之前插入结点
 private void linkBefore(int element,Node node){
  if (node==null){
   linkLast(element);
  } else {
   Node p=head,q=p.next;
   if (node.data==p.data){//node为结点时候
    head= new Node(element, p);//在头部插入元素
    size++;
   } else {
    while (p!=null){
     if (q.data==node.data) {
      p.next= new Node(element,q);//在q之前(p之后)插入一个元素
      size++;
      break;
     }
     p=p.next;
     q=p.next;
    }

   }
  }

 }

 //删除结点
 private Integer unlink(Node node){
  Integer deleteNodeData=null;
  Node p=null;
  deleteNodeData=node.data;
  if (node.data==head.data){//该节点为头结点
   p=head;
   head=p.next;
   p=null;
   size--;
  } else {
   Node q=head;
   for (p=q.next;p!=null;){//使用两个指针,p,q
    if (p.data==node.data){
     break;
    }
    q=q.next;//p始终为q的next结点
    p=q.next;
   }
   q.next=p.next;
   p=null;//删除p
   size--;
  }
  return deleteNodeData;
 }

 //数组下标是否越界
 private Boolean isElementIndex(int index){
  return index>=0&&index<size;
 }
 //插入位置是否越界
 public Boolean isPositionIndex(int index){
  return index>=0&&index<=size;
 }

 //检验下标是否越界,抛出异常
 private void checkElementIndex(int index){
  if(!isElementIndex(index)){
   try {
    throw new IndexOutOfBoundsException("下标越界");
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }

 //检验插入下标是否越界,抛出异常
 private void checkPositionIndex(int index){
  if(!isPositionIndex(index)){
   try {
    throw new IndexOutOfBoundsException("下标越界");
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }

 //返回指定位置的元素
 private Node node(int index){
  int nowIndex = 0;
  if(size>0){
   for (Node p=head;p!=null;){
    if (nowIndex==index){
     return p;
    }
    p=p.next;
    nowIndex++;
   }
  }
  return null;

 }

 public static void main(String[] args) {

  java.util.LinkedList linkedList0=new java.util.LinkedList();
  linkedList0.add(6);
  linkedList0.remove(0);
  linkedList0.size();
  linkedList0.peek();
  //linkedList0.getFirst();
  linkedList0.clear();

  //测试
  LinkedList linkedList=new LinkedList();
  linkedList.add(2);
  linkedList.add(6);
  linkedList.add(0);
  linkedList.add(3);
  linkedList.add(8);
  linkedList.add(10);
  System.out.println(linkedList.get(0));
  System.out.println(linkedList.getFirst());
  System.out.println(linkedList.getLast());
  System.out.println(linkedList.get(5));
  System.out.println(linkedList.remove(5));
  System.out.println(linkedList.remove(4));

  linkedList.remove(2);
  linkedList.remove(0);
  linkedList.remove(0);
  linkedList.remove(0);

  linkedList.add(2);
  linkedList.add(6);
  linkedList.add(0);
  linkedList.add(3);
  linkedList.add(8);
  linkedList.add(10);

  linkedList.removeFirst();
  linkedList.removeFirst();
  linkedList.removeLast();
  System.out.println(linkedList.size());

  System.out.println("遍历链表");
  linkedList.traverseList();
  linkedList.add(0,4);
  linkedList.add(0,5);
  linkedList.add(2,5);

  linkedList.add(4,5);

  linkedList.add(6,9);
  linkedList.add(8,11);
  linkedList.add(9,222);
  // linkedList.linkBefore(3,new Node(3,null));
//  linkedList.linkBefore(3,new Node(2,null));
//  linkedList.linkBefore(3,new Node(2,null));
//  linkedList.linkBefore(7,new Node(2,null));
//  linkedList.linkBefore(9,new Node(7,null));
//  linkedList.linkBefore(9,new Node(8,null));
  System.out.println("遍历链表");
  linkedList.traverseList();
  linkedList.clearList();

 }
}

以上就是Java简单实现线性表的链式存储,更多功能可参考Java集合中的LinkedList实现。

(0)

相关推荐

  • java线性表的存储结构及其代码实现

    Java数据结构学习笔记第一篇: 用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数据元素之间存在一个对多个关系 图形结构或网状结构:数据元素之间存在多个对多个的关系 对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构 顺序存储结构 链式存储结构 本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素

  • Java数据结构之线性表

    线性表是其组成元素间具有线性关系的一种数据结构,对线性表的基本操作主要有,获取元素,设置元素值,遍历,插入,删除,查找,替换,排序等.而线性表可以采用顺序储存结构和链式储存结构,本节主要讲解顺序表.单链表以及双链表的各种基本操作. 1:线性表抽象的数据类型 线性表:是由n(n>=0)个数据相同的元素组成的有限序列.线性表的定义接口如下 public interface IList<T> { /** * 是否为空 * @return */ boolean isEmpty(); /** *

  • java实现线性表及其算法

    线性表 线性表是最简单和最常用的一种数据结构,它是有n个体数据元素(节点)组成的有限序列.其中,数据元素的个数n为表的长度,当n为零时成为空表,非空的线性表通常记为: (a1,a2,- ,ai-1,ai, ai+1,-,an) 一. 线性表的顺序存储及算法 线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里,用这种方法存储的线性表称为顺序表. 1.顺序表的结构定义 public class SeqList { /* 初始空间为10 */ private stat

  • java线性表排序示例分享

    大家可以先看一下这个静态方法public static <T> void sort(List<T> list, Comparator<? super T> c) 1.先定义一个模型: 复制代码 代码如下: package model; /** * User.java *  * @author 梁WP 2014年3月3日 */public class User{    private String userName;    private int userAge; pub

  • java 线性表接口的实例详解

    java 线性表接口的实例详解 前言: 线性表是其组成元素间具有线性关系的一种线性结构,对线性表的基本操作主要有插入.删除.查找.替换等,这些操作可以在线性表的任何位置进行.线性表可以采用顺序存储结构和链式存储结构表示. 本接口的类属于dataStructure包的linearList子包.线性表接口LList声明如下,描述线性表的取值.置值.插入.删除等基本操作. package dataStructure.linearList; public interface LList<E> { bo

  • Java数据结构(线性表)详解

    线性表的链式存储与实现 实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起.这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或 删除运算时,不再需要移动元素来腾出空间或填补空缺.然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销. 单链表 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针.这里具有

  • Java实现线性表的链式存储

    本文实例为大家分享了Java实现线性表的链式存储,供大家参考,具体内容如下 链表:一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. package algorithm.datastructure.linklist; import java.util.NoSuchElementException; /* * 链表 * 物理存储上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现 * * */ public class LinkedLi

  • C语言数据结构之线性表的链式存储结构

    1.什么是线性表的链式存储结构 -链表 存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息 这个结点有:数据域和指针域 一个指针域:指向后继结点, 单链表 二个指针域: 指向前继结点,还有一个指向后继结点 双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结

  • JS实现线性表的链式表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的链式表示方法.分享给大家供大家参考,具体如下: 从上一节可以,顺序存储结构的弱点就是在插入或删除操作时,需要移动大量元素.所以这里需要介绍一下链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,所以它没有顺序存储结构的弱点,但是也没有顺序表可随机存取的优点. 下面介绍一下什么是链表. 线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素.所以,每一个数据元素除了存储自身的信息之外,还需要存储一个指向其后继的存储位置的信息.这两部分信息组成了元素的存

  • C语言线性表的链式表示及实现详解

    目录 前言 代码实现 1. 单链表的结点构造 2. 构造一个空的头结点 3. 对线性表进行赋值 4.对线性表进行销毁 5.对线性表进行重置 6.判断线性表是否为空 7.获取线性表的长度 8.获取线性表某一位置对应的元素 9.在线性表某一位置插入元素 10.删除线性表某一位置的元素 11.求线性表某一元素的前驱 12.求线性表某一元素的后继 13.打印线性表 运行结果演示 源码 前言 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,而线性表的链式存储特点则是用一组任意的存储

  • JAVA 实现二叉树(链式存储结构)

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • Java实现线性表的顺序存储

    本文实例为大家分享了Java实现线性表的顺序存储,供大家参考,具体内容如下 顺序表:用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 package algorithm.datastructure.seqlist; /*顺序表 * * 用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 * */ public class SeqList { private int length;//

  • Java 数据结构线性表之顺序存储详解原理

    目录 线性表的定义 线性表的基本运算 线性表的存储之顺序存储 定义线性表 添加元素 查找元素 删除元素 打印线性表 实现的完整代码 测试一下 线性表的定义 线性表的逻辑特征: ①有且仅有一个称为开始元素的a1,她没有前趋,仅有一个后继结点a2: ②有且仅有一个称为终端元素的an,他没有后继,只有一个直接前驱a(n-1): ③其余元素ai(2≤i≤n-1)称为内部元素,他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1). 线性表的图像表示 线性表的基本运算 线性表初始化 求表长 按索引值

  • C语言 二叉树的链式存储实例

    二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

  • C++中实现队列类链式存储与栈类链式存储的代码示例

    队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

随机推荐