Posted on 2007-02-20 12:44
dennis 阅读(2368)
评论(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。相比于链表，数组更为节约空间。毕竟链表节点还需要保存一个或者两个引用