java鏈表的頭插法和尾插法詳解

更新時間：2024年12月17日 09:32:27 作者：Sshm_666

本文介紹了鏈表的基本概念,包括節(jié)點類Listnode和鏈表類Linklist,頭插法和尾插法是兩種常見的插入節(jié)點的方法,分別通過頭指針和游標來實現(xiàn),通過示例代碼和測試,展示了鏈表的創(chuàng)建和操作過程

java鏈表的頭插法和尾插法

鏈表是由值和地址組成，地址指向下一個值的地址，

如下圖所示：

我們先定義一個節(jié)點類Listnode，里面包含值和地址屬性，再通過構造器傳值為這個值在內存中申請一塊區(qū)域。

代碼如下：

public class Listnode {
    //鏈表中一個節(jié)點的值屬性
	public int value;
//鏈表中一個節(jié)點的指針域屬性，指向下一個值的地址，因為下一塊區(qū)域是Listnode類型的所以next也是Listnode類型
	public Listnode next;
//構造器，通過值傳遞給value賦值
	public Listnode(int n) {
		this.value=n;
	}
	
}

先創(chuàng)建一個鏈表類Linklist

頭插法的思路是定義一個頭指針Listnode head=null，把第一個節(jié)點的地址通過值傳遞給它，再創(chuàng)建節(jié)點時，讓這個新節(jié)點的next指針指向舊節(jié)點，再讓這個頭指針指向新節(jié)點。

如下圖：

頭插法看如下

代碼：

public void startAdd(int n) {
//通過new實例給value創(chuàng)建一個新節(jié)點
		Listnode listnode=new Listnode(n);
//讓新節(jié)點的下一個指向舊節(jié)點，因為舊節(jié)點通過值傳遞的方式傳給head
		listnode.next=head;
//新節(jié)點通過值傳遞的方式傳給head
		head=listnode;
	}

尾插法的思路是先定義一個游標temp，游標從頭結點head開始，如果它的next指針域不是null，就讓游標指向下一個，直到游標指向next指針域為null，然后在這個節(jié)點后插入新的節(jié)點。

尾插法代碼

如下：

public void endAdd(int n) {
//通過new實例給value創(chuàng)建一個新節(jié)點
		Listnode listnode=new Listnode(n);
//判斷頭結點是否為空，空就通過值傳遞把新節(jié)點傳給頭節(jié)點，直接return不再走下面的流程
		if(head==null) {
			head=listnode;
			return;
		}
//定義游標
		Listnode temp=head;
//通過游標判斷此節(jié)點的next指針域是否為空，不是就指向下一個節(jié)點
		while(temp.next!=null) {
			temp=temp.next;
		}
//此時指向最后一個節(jié)點，讓它的next指針域指向新節(jié)點
		temp.next=listnode;
	}

總體代碼如下：

public class Linklist {
//定義頭指針
	Listnode head;
//頭插法
	public void endAdd(int n) {
		Listnode listnode=new Listnode(n);
		if(head==null) {
			head=listnode;
			return;
		}
		Listnode temp=head;
		while(temp.next!=null) {
			temp=temp.next;
		}
		temp.next=listnode;
	}
//尾插法
	public void startAdd(int n) {
		Listnode listnode=new Listnode(n);
		listnode.next=head;
		head=listnode;
	}
//把添加的值打印的方法
	public void printLink() {
		Listnode temp=head;
		while(temp!=null) {
			System.out.print(temp.value+" ");
			temp=temp.next;
		}
	}
//獲取添加多少數(shù)的方法
	public void getLength() {
		int count=0;
		if(head==null) {
			System.out.println(0);
			return;
		}
		Listnode temp=head;
		while(temp!=null) {
			count++;
			temp=temp.next;
		}
		System.out.println("你添加了"+count+"個數(shù)");
	}
}

通過test類來測試一下：

public class Test {
	public static void main(String[] args) {
		Linklist linklist=new Linklist();
		linklist.endAdd(1);
		linklist.endAdd(2);
		linklist.endAdd(3);
		linklist.endAdd(4);
		linklist.startAdd(2);
		linklist.startAdd(3);
		linklist.startAdd(4);
		linklist.printLink();
		linklist.getLength();
	}
}

結果如下：