Java实现线性表的链式存储
本文实例为大家分享了Java实现线性表的链式存储，供大家参考，具体内容如下
链表：一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
packagealgorithm.datastructure.linklist;
importjava.util.NoSuchElementException;
/*
*链表
*物理存储上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现
*
**/
publicclassLinkedList{
privateNodehead;//头节点
privateintsize;//链表长度
staticprivateclassNode{
privateintdata;
privateNodenext;
publicNode(){
}
privateNode(intdata,Nodenext){
this.data=data;
this.next=next;
}
}
//初始化空链表
publicLinkedList(){
//head=null;
}
//添加元素
publicBooleanadd(intelement){
linkLast(element);
returntrue;
}
//在某个位置之前添加元素
publicBooleanadd(intindex,Integerelement){
checkPositionIndex(index);
if(index==size){
linkLast(element);
}else{
linkBefore(element,node(index));
}
returntrue;
}
//根据下标获取元素
publicintget(intindex){
checkElementIndex(index);
returnnode(index).data;
}
//获取第一个元素
publicIntegergetFirst(){
Nodef=head;
if(f==null){
thrownewNoSuchElementException();
}else{
returnf.data;
}
}
//获取最后一个元素
publicIntegergetLast(){
if(size==0){
thrownewNoSuchElementException();
}
intindex=size-1;
returnnode(index).data;
}
//删除第一个元素
publicIntegerremoveFirst(){
Nodef=head;
if(f==null){
thrownewNoSuchElementException();
}else{
returnunlink(head);
}
}
//删除最后一个元素
publicIntegerremoveLast(){
if(size==0){
thrownewNoSuchElementException();
}
intindex=size-1;
returnunlink(node(index));
}
//根据索引删除元素
publicIntegerremove(intindex){
checkElementIndex(index);
returnunlink(node(index));
}
//销毁链表
publicvoiddestroyList(){
clearList();
}
//将链表置为空表
publicvoidclearList(){
for(Nodep=head;p!=null;){
Nodenext=p.next;//记录下一个结点
p=null;//删除当前结点
p=next;//指向下一个结点
}
size=0;
head=null;
}
//遍历链表
publicvoidtraverseList(){
for(Nodep=head;p!=null;){
System.out.println(p.data);
p=p.next;
}
}
//返回链表元素个数
publicintsize(){
returnsize;
}
//尾部添加结点
privatevoidlinkLast(intelement){
Nodecur=null,p;
if(size==0){//没有结点时
head=newNode(element,null);
size++;
return;
}
for(p=head;p!=null;){//有结点时候
cur=p;
p=cur.next;
}
cur.next=newNode(element,null);//尾部添加元素
size++;
}
//在某结点之前插入结点
privatevoidlinkBefore(intelement,Nodenode){
if(node==null){
linkLast(element);
}else{
Nodep=head,q=p.next;
if(node.data==p.data){//node为结点时候
head=newNode(element,p);//在头部插入元素
size++;
}else{
while(p!=null){
if(q.data==node.data){
p.next=newNode(element,q);//在q之前(p之后)插入一个元素
size++;
break;
}
p=p.next;
q=p.next;
}
}
}
}
//删除结点
privateIntegerunlink(Nodenode){
IntegerdeleteNodeData=null;
Nodep=null;
deleteNodeData=node.data;
if(node.data==head.data){//该节点为头结点
p=head;
head=p.next;
p=null;
size--;
}else{
Nodeq=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--;
}
returndeleteNodeData;
}
//数组下标是否越界
privateBooleanisElementIndex(intindex){
returnindex>=0&&index=0&&index<=size;
}
//检验下标是否越界，抛出异常
privatevoidcheckElementIndex(intindex){
if(!isElementIndex(index)){
try{
thrownewIndexOutOfBoundsException("下标越界");
}catch(Exceptione){
e.printStackTrace();
}
}
}
//检验插入下标是否越界，抛出异常
privatevoidcheckPositionIndex(intindex){
if(!isPositionIndex(index)){
try{
thrownewIndexOutOfBoundsException("下标越界");
}catch(Exceptione){
e.printStackTrace();
}
}
}
//返回指定位置的元素
privateNodenode(intindex){
intnowIndex=0;
if(size>0){
for(Nodep=head;p!=null;){
if(nowIndex==index){
returnp;
}
p=p.next;
nowIndex++;
}
}
returnnull;
}
publicstaticvoidmain(String[]args){
java.util.LinkedListlinkedList0=newjava.util.LinkedList();
linkedList0.add(6);
linkedList0.remove(0);
linkedList0.size();
linkedList0.peek();
//linkedList0.getFirst();
linkedList0.clear();
//测试
LinkedListlinkedList=newLinkedList();
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,newNode(3,null));
//linkedList.linkBefore(3,newNode(2,null));
//linkedList.linkBefore(3,newNode(2,null));
//linkedList.linkBefore(7,newNode(2,null));
//linkedList.linkBefore(9,newNode(7,null));
//linkedList.linkBefore(9,newNode(8,null));
System.out.println("遍历链表");
linkedList.traverseList();
linkedList.clearList();
}
}
以上就是Java简单实现线性表的链式存储，更多功能可参考Java集合中的LinkedList实现。