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实现。