Java 實現鏈表結點插入

PS:鏈表是一種數據結構,而數據結構就是一種存放數據的方式。

為什麼需要鏈表?

我們知道,數組也可以存儲數據,那麼為什麼還需要鏈表呢?接下來,我們來看看數組 和鏈表的區別:

1、數組就像身上編瞭號站成一排的人,要找第10個人很容易,根據人身上的編號很快就能找到。但插入、刪除慢,要往某個位置插入或刪除一個人時,後面的人身上的編號都要變。當然,加入或刪除的人始終末尾的也快。

2、鏈表就像手牽著手站成一圈的人,要找第10個人不容易,必須從第一個人一個個數過去。但插入、刪除快。插入時隻要解開兩個人的手,並重新牽上新加進來的人的手就可以。刪除一樣的道理。

鏈表示意圖

鏈表的建立

class TestLink{//創建一個外部類	
	private Entry head;//指向頭結點的引用
	public TestLink(){
		head = new Entry();//用結點類 new 一個頭結點
	}
	
	class Entry{//Entry 創建一個結點內部類
		int data;//定義數據塊
		Entry next;//定義地址塊
		
		public Entry(){//構造方法1
			data = -1;//對結點數據塊初始化
			next = null;//對地址初始化
		}
		public Entry(int val){//構造方法2
			data = val;//對數據塊賦值
			next = null;
		}
	}
}
public class TestDemo2 {
			public static void main(String[] args) {
				TestLink testlink = new TestLink();
				//創建一個 鏈表外部類 對象
  }
}

頭插法:從頭插入

public void insertHead(int val){
  //有這麼一個結點 
  Entry cur = new Entry(val);
  cur.next = head.next;
  head.next = cur;
  }

頭插法示意圖:

尾插法:從尾插入

public void insertTail(int val){
				//找到尾巴
				Entry cur = head;
				while(cur.next != null){//遍歷結點
					cur = cur.next;
				}
				Entry entry = new Entry(val);//得到的結點
				cur.next = entry;
			}

尾插法示意圖:

從任意結點插入

public boolean insertPos(int val,int pos){
  //1、判斷pos的合法性
  if(pos < 0 || pos >= getLength()+1){
   return false;
  }
  Entry cur = head;
  for(int i = 0;i <= pos-1;i++){
   cur = cur.next;
  }
  //cur  pos的前一個
  Entry entry = new Entry(val);
  entry.next = cur.next;
  cur.next = entry;
  return true;
  }

示意圖:

完整代碼:

package LianBiao;
class TestLink1{	
	private Entry head;//指向頭結點的引用	
	public TestLink1(){
		head = new Entry();
	}
	
	class Entry{//Entry Node 
		int data;
		Entry next;		
		public Entry(){
			data = -1;
			next = null;
		}
		
		public Entry(int val){
			data = val;
			next = null;
		}		
	}	
	
	public void insertHead(int val){
		//有這麼一個結點 
		Entry cur = new Entry(val);
		cur.next = head.next;
		head.next = cur;
		/*head.next = cur;
		cur.next = head.next;*/
	}
	
	public void insertTail(int val){
		//找到尾巴
		Entry cur = head;
		while(cur.next != null){
			cur = cur.next;
		}
		Entry entry = new Entry(val);//得到的結點
		cur.next = entry;
	}
	//得到單鏈表的長度:
	public int getLength(){
		int len = 0;
		Entry cur = head.next;
		while(cur != null){
			len++;
			cur = cur.next;
		}
		return len;
	}
	//將數據插入到指定位置
	public boolean insertPos(int val,int pos){
		//1、判斷pos的合法性
		if(pos < 0 || pos >= getLength()+1){
			return false;
		}
		Entry cur = head;
		for(int i = 0;i <= pos-1;i++){
			cur = cur.next;
		}
		//cur  pos的前一個
		Entry entry = new Entry(val);
		entry.next = cur.next;
		cur.next = entry;
		return true;
	}
	//
	
	//show()
	public void show(){
		/*Entry cur = head;
		while(cur.next != null){
			System.out.println("data:"+cur.next.data);
			cur = cur.next;
		}*/
		Entry cur = head.next;
		while(cur != null){
			System.out.println("data:"+cur.data);
			cur = cur.next;
		}
	}
	
}
public class LianBiao1 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
				TestLink1 testlink = new TestLink1();
				
				testlink.insertTail(1330);
				testlink.insertTail(110);
				//1330 110 
				testlink.insertPos(10,0);
				//10 1330 110
				
				if(testlink.insertPos(32,10000)){
					System.out.println("插入成功");
				}else{
					System.out.println("插入失敗");
				}
				
				//10 32 1330 110
				
				testlink.show();
				System.out.println(testlink.getLength());
			}
		}

輸出結果:

補充:java中創建鏈表,實現鏈表的尾部插入

我就廢話不多說瞭,大傢還是直接看代碼吧~

package test;
//目標:創建鏈表,實現鏈表結點的尾部插入
class Node_5{
  private String data;
  public Node_5 nextNode;
  public void setData(String indata){
    this.data=indata;
  }
  public String getData(){
    return this.data;
  }
  public void setNextNode(Node_5 newNode){
    this.nextNode=newNode;
  }
  public Node_5 getNextNode(){
    return this.nextNode;
  }
  public void addData(String indata){
    setData(indata);
    Node_5 node_5=new Node_5();
    Node_5 head=node_5;
    if(node_5.getData()==null){
      node_5.setData(indata);
      System.out.println(node_5.getData());
    }
    else{
      node_5.setNextNode(node_5);  
      node_5.setData(indata);
      System.out.println(node_5.getData());
    }    
  }   
}

public class T_5 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Node_5 node_5=new Node_5();
    for(int i=1;i<=3;i++){
      node_5.addData("第"+i+"結點");
    }
  }
}

以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方,望不吝賜教。