鏈表是一種根據元素節點邏輯關係排列起來的一種數據結構。利用鏈表可以保存多個數據，這一點類似於數組的概念，但是數組本身有一個缺點—— 數組的長度固定，不可改變，在長度固定的情況下首選的肯定是數組，但是在現實的開發之中往往要保存的內容長度是不確定的，那麼此時就可以利用鏈表這樣的結構來代替數組的使用。
其中單鏈表的結構
單向鏈表頭部第一個節點，有兩個變量，第一個變量是我們的數據，第二個變量是我們存放的下一個節點
首先我們創建一個數據類 ，也就是員工類(staff)。我們需要用鏈表保存它和取出；
public class staff {
public int id; //員工id
public String departmrnt; //員工部門
public String name; //員工名字
public String gender; //員工性別
public int age; //員工年齡
public staff() {
// TODO Auto-generated constructor stub
}
}
接著創建我們的鏈表節點(node)
public class node {
public int id; //節點id
public Object data; //數據
public node nextNode; //下一個節點
}
實現我們具體鏈表類
headNode 是鏈表的第一個頭節點
lastNode是最後一個節點
我們實現2個方法
一個是插入數據 public void insertdate(staff _staff) {}
根據員工id 返回員工信息 public staff getStaff(int _id ) {}
public class linkedListConcrete {
private int count=0;
private node headNOde;
private node lastNode;
/**
* 插入數據
* @param _id 具體員工id
*/
public void insertdate(int _id) {
count=count+1;
if(headNOde==null) {
headNOde=new node();
headNOde.data=_id;
headNOde.id=_id;
lastNode=headNOde;
return;
}
node nodeData=new node();
nodeData.data=_id;
nodeData.id=_id;
lastNode.nextNode=nodeData;
lastNode=nodeData;
}
/**
* 根據員工id返回對應的員工信息
* @param _id 員工id
* @return 員工
*/
public int getStaff(int _id ) {
staff tmpStaff=new staff();
if(headNOde==null) {
return 0;
}
node currentNode=null;
currentNode=headNOde;
while(true) {
if(currentNode.id==_id) {
return(int) currentNode.data;
}else {
if(currentNode.nextNode!=null) {
currentNode=currentNode.nextNode;
continue;
}else {
return 0;
}
}
}
}
}
最後我們向鏈表插入20000000條數據看看它的時間長度如何。
public class demo {
public static void main(String[] args) {
// TODO Auto-generated method stub
linkedListConcrete concrete=new linkedListConcrete();
Date d1=new Date();
SimpleDateFormat df=new SimpleDateFormat("yyyy-MM-dd HH-mm-ss");
int count=20000000;
System.out.println("開始插入"+count+"條數據");
System.out.println("當前時間:"+df.format(d1));
initLinkedList(concrete,count);
System.out.println("插入" +count+"條數據完畢");
Date d2=new Date();
System.out.println("當前時間:"+df.format(d2));
Long time=d2.getTime()-d1.getTime();
System.out.println("插入"+count+"條數據需要"+ time/1000 +"秒");
staff staff=null;
int timer=3;
int count3=0;
while(true) {
count3+=1;
Date d3=new Date();
int count2=20000000;
staff=concrete.getStaff(count2);
Date d4=new Date();
long time2=d4.getTime()-d3.getTime();
System.out.println("查找id為"+count2+"需要"+time2+"豪秒");
if(count3==timer) {
break;
}
}
}
public static void initLinkedList( linkedListConcrete _concreteLinkedList,int _count )
{
for(int i=1;i<=_count;i++) {
_concreteLinkedList.insertdate(i)
}
}
}
運行第一次
開始插入20000000條數據
當前時間:2019-09-30 01-45-56
插入20000000條數據完畢
當前時間:2019-09-30 01-46-32
插入20000000條數據需要35秒
查找id為20000000需要190豪秒
查找id為20000000需要186豪秒
查找id為20000000需要187豪秒
運行第二次
開始插入20000000條數據
當前時間:2019-09-30 01-47-34
插入20000000條數據完畢
當前時間:2019-09-30 01-48-12
插入20000000條數據需要37秒
查找id為20000000需要186豪秒
查找id為20000000需要193豪秒
查找id為20000000需要187豪秒
運行第三次
開始插入20000000條數據
當前時間:2019-09-30 01-49-32
插入20000000條數據完畢
當前時間:2019-09-30 01-50-08
插入20000000條數據需要36秒
查找id為20000000需要186豪秒
查找id為20000000需要185豪秒
查找id為20000000需要177豪秒
插入數據會創建對象會比較花時間，所以不用太在意插入數據的時間，重點是查找數據需要的時間。
經過比對查找第20000000條數據需要0.2秒
插入5000000條數據
運行第一次
開始插入5000000條數據
當前時間:2019-09-30 01-52-05
插入5000000條數據完畢
當前時間:2019-09-30 01-52-13
插入5000000條數據需要7秒
查找id為5000000需要56豪秒
查找id為5000000需要53豪秒
查找id為5000000需要52豪秒
鏈表有兩種實現方式，一種是用數組，一種是用節點的方式。你們最喜歡用那種
閱讀更多 IT大派 的文章
