 双向链表的C#实现（改进版本）
发信人: Jobs (温少), 信区: DotNET
标 题: 双向链表的C#实现（改进版本）
发信站: BBS 水木清华站 (Sun Jan 5 13:57:15 2003)
/**
*
*
@author <a href="wen">mailto:szuJobs@hotmail.com">wenshaojin</a>
@created January 2, 2003
@version 1
*
**/
using System;
using System.Collections;
using System.IO;
using Matrix.Common.Utils;
namespace Matrix.Common.Collections
{
/// <summary>
/// 双向链表
/// </summary>
/// <remarks>
/// 在需要经常中间插入和删除的数据列表，使用双向链表比ArrayList要快
/// </remarks>
public class DoublyLinkedList : IEnumerable
{
private DoublyLinkedListNode _first;
private int _count;
public DoublyLinkedList()
{
_count = 0;
_first = null;
}
/// <summary>
/// 链表中节点的数量
/// </summary>
public int Count
{
get
{
return _count;
}
}
public object this[int pos]
{
get
{
if(pos < 0 || pos >= this._count)
{
throw new ArgumentOutOfRangeException("pos");
}
DoublyLinkedListNode current = this._first;
int index = 0;
while(index < pos && current != null)
{
index ++;
current = current.Right;
}
return current.Data;
}
set
{
if(pos < 0 || pos >= this._count)
{
throw new ArgumentOutOfRangeException("pos");
}
DoublyLinkedListNode current = this._first;
int index = 0;
while(index < pos && current != null)
{
index ++;
current = current.Right;
}
current.Data = value;
}
}
private DoublyLinkedListNode FindNode(int pos)
{
//p will eventually point to k'th node
DoublyLinkedListNode p = this._first;
for(int i=0; i<pos && p != null; i++) // move p to pos'th
{
p = p.Right;
}
if(pos > 0 && p == null) // no pos'th
{
throw new ArgumentOutOfRangeException("pos");
}
return p;
}
private void InsertBefore(DoublyLinkedListNode p, object data)
{
DoublyLinkedListNode y = new DoublyLinkedListNode();
y.Data = data;
y.Left = p.Left;
y.Right = p;
p.Left.Right = y;
p.Left = y;
}
private void Remove(DoublyLinkedListNode p)
{
if(p == this._first)
{
this._first = this._first.Right;
this._first.Left = null;
}
else if(p.Right == null)
{
p.Left.Right = null;
}
else
{
p.Left.Right = p.Right;
p.Right.Left = p.Left;
}
}
/// <summary>
/// 从链表中删除指定元素
/// </summary>
/// <param name="pos"></param>
public void RemoveAt(int pos)
{
if(pos < 0)
{
throw new ArgumentOutOfRangeException("pos");
}
DoublyLinkedListNode p = FindNode(pos);
if(p == null)
{
throw new ArgumentOutOfRangeException("pos");
}
this.Remove(p);
_count --;
}
/// <summary>
/// 查找删除
/// </summary>
/// <param name="obj"></param>
/// <returns>返回删除节点数量</returns>
public int Remove(object item)
{
int itemCount = 0;
DoublyLinkedListNode p = this._first;
while(p != null)
{
object pData = p.Data;
if(item == pData
|| pData!= null && pData.Equals(item)
)
{
if(p == this._first)
{
this._first = this._first.Right;
this._first.Left = null;
}
else if(p.Right == null)
{
p.Left.Right = null;
}
else
{
p.Left.Right = p.Right;
p.Right.Left = p.Left;
}
this._count --;
itemCount ++;
}
p = p.Right;
}
return itemCount;
}
public bool Contains(object obj)
{
DoublyLinkedListNode p = this._first;
while(p != null)
{
object pData = p.Data;
if(obj == pData
|| pData!= null && pData.Equals(obj)
)
{
return true;
}
p = p.Right;
}
return false;
}
public int IndexOf(object obj)
{
int itemIndex = 0;
DoublyLinkedListNode p = this._first;
while(p != null)
{
object pData = p.Data;
if(obj == pData
|| pData!= null && pData.Equals(obj)
)
{
return itemIndex;
}
p = p.Right;
itemIndex ++;
}
return -1;
}
public void Insert(int pos, object data)
{
if(pos < 0)
{
throw new ArgumentOutOfRangeException("pos");
}
if(pos == 0)
{
DoublyLinkedListNode y = new DoublyLinkedListNode();
y.Data = data;
if(this._first == null)
{
this._first = y;
}
else
{
y.Right = this._first;
this._first.Left = y;
this._first = y;
}
}
else
{
DoublyLinkedListNode p = FindNode(pos);
InsertBefore(p, data);
}
_count ++;
}
public void MoveToFirst(int pos)
{
if(pos < 0 || this._first == null)
{
throw new ArgumentOutOfRangeException("pos"); //// no pos'th
}
if(pos == 0)
{
return;
}
DoublyLinkedListNode q = FindNode(pos);
if(q == null)
{
throw new ArgumentOutOfRangeException("pos");
}
this.Remove(q);
this._first.Left = q;
q.Right = this._first;
q.Left = null;
this._first = q;
}
public void Swap(int posA, int posB)
{
if(posA <0 || posA >= this._count)
{
throw new ArgumentOutOfRangeException("posA");
}
if(posB <0 || posB >= this._count)
{
throw new ArgumentOutOfRangeException("posB");
}
DoublyLinkedListNode p = FindNode(posA);
DoublyLinkedListNode q = FindNode(posB);
this.Swap(p, q);
}
private void Swap(DoublyLinkedListNode p , DoublyLinkedListNode q)
{
if(p == q)
{
return;
}
DoublyLinkedListNode pLeft = p.Left;
DoublyLinkedListNode pRight = p.Right;
DoublyLinkedListNode qLeft = q.Left;
DoublyLinkedListNode qRight = q.Right;
if(qRight == p)
{
p.Left = qLeft;
if(qLeft != null)
{
qLeft.Right = p;
}
if(pRight != null)
{
pRight.Left = q;
}
q.Right = pRight;
q.Left = p;
p.Right = q;
}
else if(pRight == q)
{
q.Left = pLeft;
if(pLeft != null)
{
pLeft.Right = q;
}
if(qRight != null)
{
qRight.Left = p;
}
p.Right = qRight;
p.Left = q;
q.Right = p;
}
else
{
q.Left = pLeft;
if(pLeft != null)
{
pLeft.Right = q;
}
q.Right = pRight;
if(pRight != null)
{
pRight.Left = q;
}
p.Left = qLeft;
if(qLeft != null)
{
qLeft.Right = p;
}
p.Right = qRight;
if(qRight != null)
{
qRight.Left = p;
}
}
if(this._first == p)
{
this._first = q;
}
else if(this._first == q)
{
this._first = p;
}
}
public void Add(object data)
{
DoublyLinkedListNode y = new DoublyLinkedListNode();
y.Data = data;
if(this._first == null)
{
this._first = y;
_count ++;
return;
}
DoublyLinkedListNode current = this._first;
while(current.Right != null)
{
current = current.Right;
}
current.Right = y;
y.Left = current;
_count ++;
}
/// <summary>
///
/// </summary>
/// <param name="c"></param>
public void AddRange(ICollection c)
{
foreach(object obj in c)
{
this.Add(obj);
}
}
public void Sort()
{
object[] array = new object[this._count];
this.CopyTo(array);
Array.Sort(array);
this.SetRange(0, array);
}
public void Sort(IComparer comparer)
{
object[] array = new object[this._count];
this.CopyTo(array);
Array.Sort(array, comparer);
this.SetRange(0, array);
}
public void SetRange(int index, ICollection c)
{
if(index < 0 || index >= this._count)
{
throw new ArgumentOutOfRangeException("index");
}
DoublyLinkedListNode p = this._first;
int itemIndex = 0;
while(p != null)
{
if(itemIndex >= index)
{
break;
}
p = p.Right;
itemIndex ++;
}
if(itemIndex < index || p == null)
{
return;
}
IEnumerator e = c.GetEnumerator();
while(e.MoveNext() && p != null)
{
p.Data = e.Current;
p = p.Right;
}
}
public void CopyTo(Array array)
{
DoublyLinkedListNode p = this._first;
int itemIndex = 0;
while(p != null)
{
array.SetValue(p.Data, itemIndex);
p = p.Right;
itemIndex ++;
}
}
public object[] ToArray()
{
object[] array = new object[this._count];
this.CopyTo(array);
return array;
}
public Array ToArray(Type type)
{
if(type == null)
{
throw new ArgumentNullException("type");
}
Array array = Array.CreateInstance(type, this._count);
this.CopyTo(array);
return array;
}
public void Reverse()
{
object[] objArray = new object[this._count];
this.CopyTo(objArray);
Array.Reverse(objArray);
this.SetRange(0, objArray);
}
/// <summary>
/// 清除链表
/// </summary>
public void Clear()
{
this._first = null;
_count = 0;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public DoublyLinkedListEnumerator GetEnumerator()
{
return new DoublyLinkedListEnumerator(this);
}
private class DoublyLinkedListNode
{
public object Data;
public DoublyLinkedListNode Left;
public DoublyLinkedListNode Right;
}
public class DoublyLinkedListEnumerator : IEnumerator
{
private DoublyLinkedList _list;
private DoublyLinkedListNode _location;
public DoublyLinkedListEnumerator(DoublyLinkedList list)
{
this._list = list;
}
public bool MoveNext()
{
if(this._location == null)
{
this._location = _list._first;
}
else
{
this._location = this._location.Right;
}
return this._location != null;
}
public bool MovePrevious
{
get
{
if(this._location == null)
{
this._location = _list._first;
}
else
{
this._location = this._location.Left;
}
return this._location != null;
}
}
public void Reset()
{
this._location = _list._first;
}
public object Current
{
get
{
return this._location.Data;
}
}
}
}
}
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 218.17.72.63]
上一篇
返回上一页
回到目录
回到页首
下一篇
|
[返回] 计算机科学论坛 →
计算机技术与应用 → 『 Dot NET,C#,ASP,VB 』 → 双向链表的C#实现（改进版本）
(订阅本版)
2004/11/9 2:25:00
新浪微博
