快捷導(dǎo)航

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

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

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

java鏈表的頭插法和尾插法

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

如下圖所示：

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

代碼如下：

public class Listnode {
    //鏈表中一個(gè)節(jié)點(diǎn)的值屬性
	public int value;
//鏈表中一個(gè)節(jié)點(diǎn)的指針域?qū)傩?，指向下一個(gè)值的地址，因?yàn)橄乱粔K區(qū)域是Listnode類型的所以next也是Listnode類型
	public Listnode next;
//構(gòu)造器，通過值傳遞給value賦值
	public Listnode(int n) {
		this.value=n;
	}
	
}

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

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

如下圖：

頭插法看如下

代碼：

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

尾插法的思路是先定義一個(gè)游標(biāo)temp，游標(biāo)從頭結(jié)點(diǎn)head開始，如果它的next指針域不是null，就讓游標(biāo)指向下一個(gè)，直到游標(biāo)指向next指針域?yàn)閚ull，然后在這個(gè)節(jié)點(diǎn)后插入新的節(jié)點(diǎn)。

尾插法代碼

如下：

public void endAdd(int n) {
//通過new實(shí)例給value創(chuàng)建一個(gè)新節(jié)點(diǎn)
		Listnode listnode=new Listnode(n);
//判斷頭結(jié)點(diǎn)是否為空，空就通過值傳遞把新節(jié)點(diǎn)傳給頭節(jié)點(diǎn)，直接return不再走下面的流程
		if(head==null) {
			head=listnode;
			return;
		}
//定義游標(biāo)
		Listnode temp=head;
//通過游標(biāo)判斷此節(jié)點(diǎn)的next指針域是否為空，不是就指向下一個(gè)節(jié)點(diǎn)
		while(temp.next!=null) {
			temp=temp.next;
		}
//此時(shí)指向最后一個(gè)節(jié)點(diǎn)，讓它的next指針域指向新節(jié)點(diǎn)
		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+"個(gè)數(shù)");
	}
}

通過test類來測(cè)試一下：

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();
	}
}

結(jié)果如下：