頭插法
-
簡(jiǎn)介
頭插法建立單鏈表的算法雖然簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入數(shù)據(jù)的順序不一致。若希望兩者次序一致，可采用尾插法髓窜。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)欺殿，如圖所示寄纵。
頭插法圖解.jpg 代碼實(shí)現(xiàn)
//鏈表節(jié)點(diǎn)類實(shí)現(xiàn)
public class Node<T> {
/**
* 下一個(gè)節(jié)點(diǎn)
*/
Node<T> next;
/**
* 節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)
*/
T val;
/**
*
* @param val data域
* @param next 指針域
*/
Node(T val,Node<T> next){
this.val=val;
this.next=next;
}
boolean hasNext(){
return this.next!=null;
}
}
//單鏈表的操作類
public class LinearList<T> {
//鏈表頭結(jié)點(diǎn)
Node<T> head;
public LinearList(){
//空鏈表
this.head=new Node<T>(null,null);
}
//頭插法 鏈表 指針指向最this.head
void add(T val){
this.head=new Node<T>(val,this.head);
}
public static void main(String[] args) {
LinearList<Integer> list = new LinearList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
Node<Integer> head = list.head;
while (head.hasNext()) {
System.out.println(head.val);
head = head.next;
}
}
}
尾插法
-
介紹
頭插法建立單鏈表的算法雖然簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入數(shù)據(jù)的順序不一致脖苏。若希望兩者次序一致程拭，可采用尾插法。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上棍潘，為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)恃鞋，如圖所示。
尾插法.jpg
- C語(yǔ)言代碼
LinkList CreatList2(LinkList &L){
//從表頭到表尾正向建立單鏈表L,每次均在表尾插入元素
int x; // 設(shè)元素類型為整型
L=(LinkList)malloc(sizeof(LNode));
LNode *s, *r=L; //r 為表尾指針
scanf ("%d", &x); //輸入結(jié)點(diǎn)的值
while (x!=9999) { //輸入 9999 表示結(jié)束
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s; //r指向新的表尾結(jié)點(diǎn)
scanf ("%d", &x);
}
r->next = NULL; //尾結(jié)點(diǎn)指針置空
return L;
}
