Posted on 2007-02-20 12:44
dennis 閱讀(2373)
評論(1) 編輯 收藏 所屬分類:
數據結構與算法
數組的兩大缺點：
1。若改變數組的大小就要創建一個新的數組，并需要從原數組復制所有的數據到新的數組
2。數組元素在內存中依次順序存儲，這意味著向數組插入一項要移動數組中的其他元素
因此，我們使用鏈式結構，鏈式結構是存儲數據的結點以及指向其他節點的指針的集合。如此一來，節點可以位于內存的任意位置，而且從一個節點到另一個節點的傳遞可以通過在結構中存儲節點間引用來實現。
一。單向鏈表
1。鏈表：
如果一個節點包含指向另一個節點的數據值，那么多個節點可以連接成一串，只通過一個變量訪問整個節點序列，這樣的節點序列稱為鏈表（linked list）
2。單向鏈表：
如果每個節點僅包含其指向后繼節點的引用，這樣的鏈表稱為單向鏈表。
一個整型單向鏈表的實現：
?
package
?com.sohu.blog.denns_zane.list;
/**?*/
/**
?*?
@author
?dennis
?*?@Description?整型單向鏈表節點
?
*/
public
?
class
?IntSLLNode?
{
????
public
?
int
?info;?
//
?用戶信息
????
public
?IntSLLNode?next;?
//
?下一個節點，自引用
????
/**?*/
/**
?????*?
@param
?info
?????*?
@param
?next
?????
*/
????
public
?IntSLLNode(
int
?info,?IntSLLNode?next)?
{
????????
this
.info?
=
?info;
????????
this
.next?
=
?next;
????}
????
/**?*/
/**
?????*?
@param
?info
?????
*/
????
public
?IntSLLNode(
int
?info)?
{
????????
this
(info,?
null
);
????}
}
/**?*/
/**
?*?
?
*/
package
?com.sohu.blog.denns_zane.list;
/**?*/
/**
?*?
@author
?dennis
?*?desc:?整型單向鏈表
?
*/
public
?
class
?IntSLList?
{
????
protected
?IntSLLNode?head,?tail;
????
public
?IntSLList()?
{
????????head?
=
?tail?
=
?
null
;
????}
????
public
?
boolean
?isEmpty()?
{
????????
return
?head?
==
?
null
;
????}
????
/**?*/
/**
?????*?@description?增加新節點，并設置它的next為原head
?????*?
@param
?el
?????
*/
????
public
?
void
?addToHead(
int
?el)?
{
????????head?
=
?
new
?IntSLLNode(el,?head);
????????
if
?(tail?
==
?
null
)
????????????tail?
=
?head;
????}
????
/**?*/
/**
?????*?@description?增加新節點，并設置原tail的next為新節點
?????*?
@param
?el
?????
*/
????
public
?
void
?addToTail(
int
?el)?
{
????????
if
?(
!
isEmpty())?
{
????????????tail.next?
=
?
new
?IntSLLNode(el);
????????????tail?
=
?tail.next;
????????}
?
else
?
{
????????????head?
=
?tail?
=
?
new
?IntSLLNode(el);
????????}
????}
????
public
?
int
?deleteFromHead()?
{
????????
if
?(head?
==
?
null
)
????????????
throw
?
new
?NullPointerException();
????????
int
?el?
=
?head.info;
????????
if
?(head?
==
?tail)
????????????head?
=
?tail?
=
?
null
;
????????
else
????????????head?
=
?head.next;
????????
return
?el;
????}
????
public
?
int
?deleteFromTail()?
{
????????
if
?(head?
==
?
null
)
????????????
throw
?
new
?NullPointerException();
????????
int
?el?
=
?tail.info;
????????
if
?(head?
==
?tail)
????????????head?
=
?tail?
=
?
null
;
????????
else
?
{
????????????IntSLLNode?temp;
????????????
for
?(temp?
=
?head;?temp.next?
!=
?
null
?
&&
?temp.next?
!=
?tail;?temp?
=
?temp.next)
????????????????tail?
=
?temp;
????????????System.out.println(tail.info);
????????????tail.next?
=
?
null
;
????????}
????????
return
?el;
????}
????
public
?
void
?printAll()?
{
????????
for
?(IntSLLNode?temp?
=
?head;?temp?
!=
?
null
;?temp?
=
?temp.next)
????????????System.out.print(temp.info?
+
?
"
?
"
);
????}
????
public
?
boolean
?isInList(
int
?el)?
{
????????
for
?(IntSLLNode?temp?
=
?head;?temp?
!=
?
null
;?temp?
=
?temp.next)?
{
????????????
if
?(temp.info?
==
?el)
????????????????
return
?
true
;
????????}
????????
return
?
false
;
????}
????
/**?*/
/**
?????*?
@param
?el
?????
*/
????
public
?
void
?delete(
int
?el)?
{
????????
if
?(
!
isEmpty())?
{
????????????
if
?(head?
==
?tail?
&&
?head.info?
==
?el)
????????????????head?
=
?tail?
=
?
null
;
????????????
else
?
if
?(head.info?
==
?el)
????????????????head?
=
?head.next;
????????????
else
?
{
????????????????IntSLLNode?pred,?temp;
//
?pred為找的節點的前一節點，temp即為找到的節點
????????????????
for
?(pred?
=
?head,?temp?
=
?head.next;?temp?
!=
?
null
;?pred?
=
?pred.next,?temp?
=
?temp.next)?
{
????????????????????
if
?(temp.info?
==
?el)?
{
????????????????????????pred.next?
=
?temp.next;?
//
?前一節點的next設置為當前節點的next
????????????????????????
if
?(temp?
==
?tail)
????????????????????????????tail?
=
?pred;
????????????????????}
????????????????}
????????????}
????????}
????}
}
二。雙向鏈表
單向鏈表的deleteFromTail()方法指出了單向鏈表的固有問題，這種鏈表的節點僅僅包含指向后繼節點的引用，所以無法立即訪問它的前驅節點，不得不掃描整個鏈表來查找此前驅節點。因此，我們重新定義鏈表節點，包含兩個引用，一個指向前驅節點，一個指向后驅節點，也就是——雙向鏈表。
一個整型雙向鏈表的實現：
/**?*//**
?*?
?*/
package?com.sohu.blog.denns_zane.list;
/**?*//**
?*?@author?dennis?desc:雙向鏈表節點
?*/
public?class?IntDLLNode?{
????public?int?info;
????public?IntDLLNode?prev,?next;
????/**?*//**
?????*?@param?info
?????*?@param?prev
?????*?@param?next
?????*/
????public?IntDLLNode(int?info,?IntDLLNode?next,?IntDLLNode?prev)?{
????????super();
????????this.info?=?info;
????????this.prev?=?prev;
????????this.next?=?next;
????}
????public?IntDLLNode(int?info)?{
????????this(info,?null,?null);
????}
}
/**?*//**
?*?
?*/
package?com.sohu.blog.denns_zane.list;
/**?*//**
?*?@author?dennis
?*?
?*/
public?class?IntDLList?{
????private?IntDLLNode?head,?tail;
????public?IntDLList()?{
????????head?=?tail?=?null;
????}
????public?boolean?isEmpty()?{
????????return?head?==?null;
????}
????public?void?addToHead(int?el)?{
????????if?(head?==?null)
????????????head?=?new?IntDLLNode(el);
????????else?{
????????????head?=?new?IntDLLNode(el,?head,?null);
????????????head.next.prev?=?head;
????????}
????????if?(tail?==?null)
????????????tail?=?head;
????}
????public?void?addToTail(int?el)?{
????????if?(!isEmpty())?{
????????????tail?=?new?IntDLLNode(el,?null,?tail);
????????????tail.prev.next?=?tail;
????????}?else
????????????head?=?tail?=?new?IntDLLNode(el);
????}
????public?int?removeFromTail()?{
????????if?(head?==?null)
????????????throw?new?NullPointerException();
????????int?el?=?tail.info;
????????if?(head?==?tail)
????????????head?=?tail?=?null;
????????else?{
????????????tail?=?tail.prev;
????????????tail.next?=?null;
????????}
????????return?el;
????}
????public?int?removeFromHead()?{
????????if?(head?==?null)
????????????throw?new?NullPointerException();
????????int?el?=?head.info;
????????if?(head?==?tail)
????????????head?=?tail?=?null;
????????else?{
????????????head?=?head.next;
????????????head.prev?=?null;
????????}
????????return?el;
????}
????public?boolean?isInList(int?el)?{
????????if?(head?==?null)
????????????return?false;
????????IntDLLNode?temp;
????????for?(temp?=?head;?temp?!=?null;?temp?=?temp.next)?{
????????????if?(temp.info?==?el)?{
????????????????return?true;
????????????}
????????}
????????return?false;
????}
????public?void?delete(int?el)?{
????????if?(head?==?null)
????????????throw?new?NullPointerException();
????????IntDLLNode?temp;
????????for?(temp?=?head;?temp?!=?null;?temp?=?temp.next)?{
????????????if?(temp.info?==?el)?{
????????????????if?(temp?==?head)?{
????????????????????head.next.prev?=?null;
????????????????????head?=?head.next;
????????????????}?else
????????????????????temp.prev.next?=?temp.next;
????????????}
????????}
????}
????public?void?printAll()?{
????????IntDLLNode?temp;
????????for?(temp?=?head;?temp?!=?null;?temp?=?temp.next)?{
????????????System.out.print(temp.info?+?"?");
????????}
????????System.out.println();
????}
}
三。跳轉表，循環表，自組織表（略）
四。結論
1。需要隨機訪問某元素，數組更為合適
2。需要動態分配內存，經常改變結構，鏈表更為合適
3。相比于鏈表，數組更為節約空間。畢竟鏈表節點還需要保存一個或者兩個引用