線性表的鏈式存儲——算法與數據結構

鏈表是什麼

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（Node）（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域(data)，另一個是存儲下一個結點地址的指針域。 相比於線性表順序結構，操作複雜。由於不必須按順序存儲，鏈表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間。

鏈表的分類

單鏈表

單向循環鏈表

雙向鏈表

雙向循環鏈表

線性表的鏈式存儲結構

頭節點和頭指針

1、頭節點指的是鏈表中的第一個節點，有真實頭節點和虛擬頭節點。
1.1 真實頭節點：

真實頭節點的第一個節點存有數據
1.2 虛擬頭節點

虛擬頭節點的第一個節點不能存放數據
2、頭指針：存放頭節點的地址

插入元素（頭插法）

頭插法就是在虛擬頭節點的後一個插入新的元素，每次插入的新元素，都在最前面，最開始虛擬頭節點的next指向為NULL。

當有新的元素進來時，它的指針域將會給新節點的指針域指向一下個。而虛擬頭節點的指針域則指向新元素的數據域地址。同時rear（尾指針）指向新插入的元素。

再插入一個元素B，首先封裝成Node節點，然後頭節點的next給B的next指向A，然後頭節點next再指向新元素。

可以看出rear（尾指針）依舊指向最開始進來的元素A，所以可知，第一個頭插法進來的元素絕對是尾指針。 它指向的元素是尾節點。

插入元素（尾插法）

尾插法就是在元素的後面插入一個新元素，然後上一節點的指針域指向新元素，同時新元素的指針域指向下一個元素。

頭插尾插結合

當插入第一個元素A時，進行頭插法，頭節點的next指向元素A，A的next指向下一個，同時rear指向A。當插入B元素時，頭插，B的next指向A，頭節點指向B的地址。插入C是採取尾插，A的next給C的next。同時A的next指向C。rear（尾指針）指向C。頭插法插入D時，D的next指向B，頭節點的next指向D。

一般插入

如圖：在B和A之間插入元素C

刪除元素（頭刪）

如圖：若果想要刪除A元素，那麼可以讓頭節點的指針域指向B，但是A的指針域此時也指向B，所以要真正刪除A元素，還需要讓的指針域指向NULL。

假設此時只有A一個元素，想要刪除掉他的話，頭指針和尾指針會怎麼變化呢？

圖中可以看出鏈表中有兩個節點一個元素A。如果要刪除A的話，head的next指向為空，然後將rear（尾指針重置為0的狀態即誰也不指，則已刪除元素A）

刪除元素（尾刪）

現在有三個元素A,B,C，對他們依次進行尾刪。

首先刪除A元素（size-1），我們可以先將尾指針rear指向C，然後將C的next指向NULL，來刪除A，刪除C時，將rear指向B，B的next指向NULL，刪除B時，rear指向虛擬頭節點，然後頭節點的next指向NULL。

刪除元素（一般刪除）

在上面三個元素，四個節點中刪除C元素，首先要找到C元素的位置，找到之後，讓B的next指向A，同時將C的next置為NULL，這樣就可以刪除C元素了。

LinkedList實現的也是List接口，所以它得實現List中的方法。

其中，需要有一個Node類作為內部類，來對元素進行封裝，包含它的數據域（data），指針域（next）

<code>
private
 
class
 
Node
{
        E 
data
;  
        Node next;   
        
public
 Node(){
            
this
(
null
,
null
);
        }
        
public
 Node(E 
data
,Node next){
            
this
.
data
 = 
data
;
            
this
.next = next;
        }

         
        
public 
 String toString() {
            
return
 
data
.toString();
        }
    }/<code>

定義三個變量，head指的是頭指針，rear是尾指針，size是其中元素的個數，創建一個無參的構造方法，初始化一個節點，包括它的虛擬頭節點，它的尾指針和頭指針指向同一個節點對象，此時裡面的元素為0

<code>
public
 
class
 
LinkedList
<
E
> 
implements
 
List
<
E
> 
{
 
    
private
 
class
 
Node
{
        E data;  
        Node next;   
        
public
 
Node
 
()
{
            
this
(
null
,
null
);
        }
        
public
 
Node
(E data,Node next)
{
            
this
.data = data;
            
this
.next = next;
        }

         
        
public
 String 
toString
()
 
{
            
return
 data.toString();
        }
    }
	
	
private
 Node head;   
    
private
 Node rear;   
    
private
 
int
 size;    

	
public
 
LinkedList
()
{
        head = 
new
 Node();
        rear = head;
        size=
0 
;
    }

    
public
 
LinkedList
(E[] arr)
{
        head = 
new
 Node();
        rear = head;
        size =
0
;
    }

}

/<code>

getSize()

獲取鏈表中的元素個數，可以藉助Arrays中的getSize()方法。因為鏈表也是線性表的一種。

<code> 
    
public
 
int
 
getSize
()
 
{
        
return
 size;
    }
/<code>

isEmpty()

鏈表為空時，它的next指向為NULL，同時裡面的元素個數為0，所以它的判空條件size=0,head.next=null即如圖：

<code>	 
    
public
 
boolean
 
isEmpty
()
 
{
        
return
 size==
0
&&head.next==
null
;
    }
/<code>

add(int index,E e)

首先要對index的位置進行判斷是否合法，然後看是頭插還是尾插或者是一般插入，當是頭插法的時候，將head的next給插入節點的next然後在讓head指向node。當元素個數為0的時候，讓尾指針指向新的元素。

<code>
public
 
void
 
add
(
int
 index, E e
)
 {
        
if
(index<
0
||index>size){
            
throw 
 
new
 IllegalArgumentException(
"插入角標非法！"
);
        }
         
        Node node = 
new
 Node(e, 
null
);
        
if
(index==
0
){
            node.next = head.next;
            head.next = node;
           rear.next = node;
        }
if
(size==
0
){
        	rear = node;
        }
/<code>

當插入元素是最後一個，則採用尾插法rear.next指向新插入的元素，然後尾指針後移

<code>
else
 
if
(index==size){
	rear.
next
 = node;
	rear = rear.
next
;
}/<code>

當使用一般插入的時候，首先你要找到你要插入位置的前驅的節點。找到它之後，將它的next給插入的元素然後指向下一個元素，再讓它的前驅節點和它連接在一起。

<code>
else
{
	Node p = head;
	
for
(int i=
0
;inext;
	}
		node. 
next
 = p.
next
;
		p.
next
 = node;
	}
	size++;
}


/<code>

addFirst(E e)

直接用add(int index,E e)

<code>
public
 
void
 
addFirst
(
E e
)
{
	
add
(
0
,e);
}
/<code>

addLast(E e)

<code>
public
 
void
 
addLast
(
E e
)
{
	
add
(size,e);
}
/<code>

get(int index)

獲取在index出的元素值，首先判斷index的合法性，當index==0時，直接返回虛擬頭節點next裡面的data

如果index= =size-1時，直接返回尾指針裡的data。如果是一般情況的話，首先要找到它的前驅節點，然後再獲取它裡面的data。

<code>
public
 E 
get
(int index){
	
if
(index<
0
||index>=size){
		
throw
 new IllegalArgumentExcepiton(
"查找角標非法"
);
	}
	
if
(index==
0
){
		
return
 head.next.
data
;
	}
else
 
if
(index==size-
1
){
		
return
 rear.next;
	}
else
{
		Node p =head;
		
for
(int i=
0
;i<=index;i++){
			p = p.next;
		}
		
return
 p.
data
;
	}
}
/<code>

getFirst()

<code>
public
 E 
getFirst
(
)
{
	
return
 
get
(
0
);
}/<code>

getLast()

<code>
public
 E 
getLast
(
)
{
	
return
 
get
(size
-1
);
}/<code>

set(int index,E e)

將index出的元素的值更新為e,Node o = head 讓他找到index的前驅的元素，使p.next指向找到的元素p.data=e就完成了值的更新。

<code>public void set(
int
 
index
,E e){
	
if 
(
index
<
0
||
index
>=size){
		throw new IllegalArgumentException(
"index參數不合法"
);
	}
	
if
(
index
==
0
){
		head.next.data = e;
	}
else
 
if
(
index
==size-
1
){
		rear.data = e;
	}
else
{
		Node p = head;
		
for
(
int
 i=
0
;i<
index
;i++){
			p = p.next;
		}
		p.data = e;
	}
}
/<code>

find(E e)

尋找e的位置，這裡沒有給具體的位置，所以需要使用到while循環，當Node p = head，循環的條件是當p走到最後一個位置時就尋找結束，即當p.next=null;時跳出循環，p的起始位置是在虛擬頭節點出，index=-1，所以它在第一個有效元素的時候，index=index+1;當找到對應的元素條件應滿足p.data=e;

<code>
public
 int find(E e){
	int index = -
1
;
	
if
(isEmpty()){
		
return
 -
1
;
	}
	Node p = head;
	
while
(p.next!=
null
){
		p = p.next;
		index++;
		
if
(p.
data
=e){
			
return
 index;
		}
	}
	
return
 -
1
;
}
/<code>

boolean contains(E e)

<code>
public
 
boolean
 
contains
(E e)
{
	
return
 find(e)!=-
1
;
}/<code>

remove(int index)

刪除元素，一共有三種情況，第一種是頭元素，第二種是尾元素，第三種就是一般刪除

當頭刪時，Node p 來存放head.next（即刪除的元素）,然後head.next=p.next將head和刪除元素的一下個進行連接，然後斷開刪除元素和下一個元素的連接並將p置空,尾刪：找到刪除元素的前一個，然後前驅的next置為null，並將rear指針移動回來，一般刪除，創建一個Node p用來移動，當找到元素的前驅時，讓前驅的next指向刪除元素的next，並將刪除元素和下一個元素的連接斷開。

<code>public E 
remove
(int index){
	
if
(index=size){
		throw new IllegalArgumentException(
"index參數不合法"
);
	}
	E temp = null;	//用來存儲刪除元素的data
	
if
(index == 
0
){
		Node p = head.
next
;
		temp = p.data;
		head.
next
 = p.
next
;
		p.
next
 = null;
		p = null;
		
if
(size==
1
){
			rear=head;
		}
	}
else
 
if
(index==size
-1
){
		Node p = head;
		temp = rear.data;
		
while
(p.
next 
!=rear){
			p=p.
next
;
		}
		p.
next
=null;
		rear = p;
	}
else
{
		Node p = head;
		
for
(int i=
0
;inext;
		}
		Node del = p.
next
;
		temp = del.data;
		p.
next
 = del.
next
;
		del.
next
 = null;
		del = null;
	}
	size 
	
return
 temp;
}
/<code>

removeFirst()

<code>
public
 E 
removeFirst
(
)
{
	
return
 
remove
(
0
);
}
123
/<code>

removeLast()

<code>
public
 E 
removeLast
 
()
{
	
return
 removeLast(size
-1
);
}/<code>

removeElement(E e)

通過使用find(e)來找到對應的位置，然後remove(index)

<code>
publc 
void
 
removeElement
(
E e
)
{
	
int
 index = find(e);
	
if
(index==
-1
){
		
throw
 
new
 IllegalArgumentException(
"元素不存在"
);
	}
	
remove
(index);
}
/<code>

clear()

清空,只需將head.next置空，讓rear和head相同,size=0;

<code>
public
 
void
 
clear 
(
)
{
	head.next = 
null
;
	rear = head;
	size = 
0
;
}/<code>

測試

<code>
public
 
class
 
Main
 {

    
public
 
static
 
void
 
main
(String[] args)
 
{
        LinkedList 
list
 = 
new
 LinkedList();
        
for
 (
int
 i = 
1
; i <= 
10
; i++) {
            
list
.addFirst(i);
        }
        System.out.println(
list
);
        
for 
 (
int
 i = 
11
; i 
15
 ; i++) {
            
list
.addLast(i);
        }
        System.out.println(
list
);
        System.out.println(
list
.getFirst());
        System.out.println(
list
.getLast());
        
for
 (
int
 i = 
1
; i <= 
5
 ; i++) {
            
list
.removeFirst();
            
list
.removeLast();
        }
        System.out.println(
list
);
        
list
.removeFirst();
        
list
.removeFirst();
        
list
.removeFirst();
        
list
.removeFirst();
        
list
.removeFirst();
        System.out.println(
list
);
    }
}
/<code>

運行結果

<code>歡迎訪問我的博客/<code>