JAVA單向鏈表實現

JAVA單向鏈表實現

單向鏈表

鏈表和數組一樣是一種最常用的線性數據結構，兩者各有優缺點。數組我們知道是在內存上的一塊連續的空間構成，所以其元素訪問可以通過下標進行，隨機訪問速度很快，但數組也有其缺點，由于數組的內存是一次性申請的，就像基本數據類型一樣，一次性申請所需的空間，在數據量變動很大的時候就容易導致預先申請的內存不夠或內存浪費。在者就是在存的是有序數列時進行數據插入會比較麻煩，所以鏈表就是為了彌補數組的不足的一種數據結構。相反的，鏈表對于變動很大的數據有很大的適應性，而且其對于數據插入和刪除很方便。而鏈表的缺點就是對于內存的浪費，鏈表除了存儲需要的數據還要存儲額外的指針。鏈表的節點示意圖如下：

?

看到指針你可能會想：“我們這不是java語言嗎？沒有指針啊！”，沒錯！在我對java了解不是很深的時候我也這么想，但是我要說的是java雖然不允許程序員像c/c++那樣使用指針，但java語言本身的實現還是離不開指針的（變量名其實就是指向jvm中一塊內存的指針，我就不詳述）。請看以下節點的代碼：

//節點數據結構
    private class Node{
  private Object data=null;//數據域
  private Node next=null;//下一個節點
  private Node(Object data) {
   this.data=data;
  }
 }

這里的節點class我是寫成inner class的形式，后面有完整代碼。還有一點就是這里object類型，這里也可以使用泛型

//鏈表數據結構
public class SingleLinkList {
 int size=0;//鏈表長度，可有可無，有的話很容易實現很多鏈表的特殊操作
 Node head=null;//頭節點
 public SingleLinkList() {
  this.size=0;this.head=null;
 }
}

有了這兩個類，然后再來實現鏈表的一些基本操作：插入頭節點，刪除頭節點，刪除指定節點，查找指定節點。直接看完整源代碼。

package singleLinkList;
?
public class SingleLinkList {
?
 int size=0;//鏈表長度
 Node head=null;
 
 public SingleLinkList() {
  this.size=0;this.head=null;
 }
  
 //節點數據結構
 private class Node{
  private Object data=null;//數據域
  private Node next=null;//下一個節點
  private Node(Object data) {
   this.data=data;
  }
 }
 
 //表頭添加元素
 public Object addHead(Object data) {
  Node newHead=new Node(data);
  if(size==0) {
   this.head=newHead;
  }
  else {
   newHead.next=this.head;
   this.head=newHead;
  }
  size++;
  return data;
 }
 
 //刪除表頭元素
 public Object deleteHead() {
  if(size>0) {
  Node node=this.head;
  this.head=this.head.next;
  size--;
  }
  return null;
 }
 
 //查找指定元素
 public Node findData(Object data) {
  if(size==0)return null;
  Node cur=this.head;