数据结构(二)---单链表的实现---java版

时间:2022-09-15 10:33:12
package com.cn.hbut.domain;

//节点设置
public class Node {
Object data;
Node next;
//初始化一个数据域以及next域均为null的节点
public Node() {
this.data=null;
this.next=null;
}
//生成元素为obj,引用值为n的新节点
public Node(Object obj,Node n){
data=obj;
next=n;

}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}


}

----------------------------------------------------------------------------------

具体的实现

package com.cn.hbut.daoImpl;


import java.util.LinkedList;


import com.cn.hbut.dao.DefineList;
import com.cn.hbut.domain.Node;


/**
 * @author Administrator
 * description:
 * 单链表的具体实现
 */
public class SLinkList implements DefineList{
Node head;
int size;
//创建一个单链表,头结点的数据域以及指针域均为null
public SLinkList() {
head= new Node();
size=0;
}
//创建一个单链表,其长度为该数组的长度,节点的值为该数组的值
public SLinkList(Object []a){
//一个单节点
Node p;
int i,n=a.length;
//创建空的头结点
head =  new Node();
for(i=n-1;i>=0;i--){
p= new Node(a[i],head.getNext());
head.setNext(p);
}
size=n;
}
//取第i个节点
public Node index(int i){
Node p;
int j;
//索引的节点范围不合法,返回null
if(i<0||i>size)
p=null;
//第一个节点,为头结点
else if(i==0){
p=head;
}
//在范围内的索引
else{
p=head.getNext();
j=1;
while(p!=null&&j<i){
p=p.getNext();
j++;
}


}
return p;
}
@Override
public void clear() {
head=new Node();
size=0;
}
//获取第i个节点存的数据
@Override
public Object gete(int i) {
if(i<0||i>size){
return null;
}
return index(i).getData();
}


@Override
public int length() {
return size;
}

//根据元素,定位该元素在链表中的位置
@Override
public int loc(Object e) {
int j=1;
Node p= head.getNext();
//p的节点的值不为e,并且p的next不为null
while((!p.getData().equals(e))&&(p.getNext()!=null)){
j++;
p=p.getNext();
}
//索引到最后一个节点,若该节点的值还不是e,则该链表中不存在该e
if((p.getNext())==null&&(!p.getData().equals(e))){
return -1;
}
return j;
}
//在某个元素位置后面插入一个节点
@Override
public boolean inset(int loc, Object e) {
Node index=index(loc);
if(index==null)
return false;
Node now =new Node(e,index.getNext());
index.setNext(now);
size++;
return true;
}
//删除某个位置的节点
@Override
public Object dele(int loc) {
//位置不合法,返回null
if(loc<0||loc>size)
return null;
//待删除的节点
Node q = index(loc);
//待删除的前一个节点
Node p = index(loc-1);
p.setNext(q.getNext());
size--;
return q;
}


@Override
public boolean full() {
return false;
}


@Override
public boolean empty() {
return head.getNext()==null;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}

}


------------------------------------------------------------------------------

//测试单链表
}
@Test
public void testSlinkList(){
Integer [] a= {1,5,3,4};
//创建单链表
SLinkList  list = new SLinkList(a);
System.out.println(list.loc(3));
list.inset(2, 8);
//1 5 8 3 4
System.out.println("您删除的元素是:"+((Node)list.dele(2)).getData());
Object obj=list.gete(2);
System.out.println(obj);
System.out.println(((SLinkList) list).getSize());

}