java 数据结构之单链表
一、单链表的概念
链表是最基本的数据结构,其存储的你原理图如下图所示
上面展示的是一个单链表的存储原理图,简单易懂,head为头节点,他不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用,而每个节点中都有一个next引用,指向下一个节点,就这样一节一节往下面记录,直到最后一个节点,其中的next指向null。
二、单链表的实现:
首先先定义一个Entry类吧!
class Entry<T>{
private T value; //运用泛型定义数据类型
private Entry next; //定义next域
public Entry(){
next = null;
}
public Entry(T value){
this.value=value;
this.next=null;
}
}
定义一个单链表并实现一些基本方法:
class MyLinkedList<T>{
private Entry head; //定义一个头结点
private int len; //定义单链表长度
public MyLinkedList(){
head=new Entry();
}
public void insertHead(T value){ //头插法
Entry entry=new Entry();
entry.next=head.next;
head.next=entry;
}
public void insertTail(T value){ // 尾插法
Entry entry=new Entry();
Entry i;
for( i=head;i.next!=null;i=i.next);
i.next=entry;
}
public int getSize(Entry a){ //获得单链表长度
int count=0;
for(Entry entry=a.head.next;entry!=null;entry=entry.next){
count++;
}
len=count;
return len;
}
public void insert(int pos,T value){//按位置插入
if(pos < 0 || pos > len-1){//判断插入位置是否合法
return;
}
Entry e = new Entry();//申请新节点
e.value=(Comparable) value;
Entry n = head;
for(int i = 0;i <= pos-1;i++){//遍历找到插入位置
n = n.next;
}
e.next = n.next;
n.next = e;
}
public boolean remove(T value){ //删除单链表中一个指定值
int count=-1;
for(Entry entry=head.next;entry!=null;entry=entry.next){
if(entry.next.value==value){
count++;
Entry p=entry.next;
entry.next=p.next;
p.value=null;
break;
}
}
if(count==-1){
return false;
}else{
return true;
}
}
//判断单链表是否有环
public boolean circle(){
Entry p=new Entry();
Entry q=new Entry();
while(p!=null||q!=null){
p=p.next;
q=q.next.next;
if(p==q){
return true;
}
}
return false;
}
}
以上就是基本单链表的构造。