using System;
using System.Collections.Generic;
using System.Text;
namespace DataStructure
{
/// <summary>
/// 雙向鏈表類
/// </summary>
/// <typeparam name="T"></typeparam>
class DoubleLinkList<T> : IListDS<T>
{
private DoubleLinkItem<T> head;
public DoubleLinkItem<T> Head
{
get { return head; }
set { head = value; }
}
/// <summary>
/// 獲取雙向鏈表長度
/// </summary>
/// <returns></returns>
public int GetLength()
{
if (IsEmpty())
return 0;
int length = 1;
DoubleLinkItem<T> temp = head;
while (temp.Next != null)
{
temp = temp.Next;
length++;
}
return length;
}
/// <summary>
/// 清除雙向鏈表所有數據
/// </summary>
public void Clear()
{
if (!IsEmpty())
{
DoubleLinkItem<T> temp = head;
while (temp.Next != null)
{
temp = temp.Next;
temp.Last = null;
}
temp = null;
}
}
/// <summary>
/// 判斷雙向鏈表是否為空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if (head == null)
return true;
else
return false;
}
/// <summary>
/// 判斷雙向鏈表是否已滿
/// </summary>
/// <returns></returns>
public bool IsFull()
{
return false;
}
/// <summary>
/// 在雙向鏈表的尾端添加一個新數據
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
DoubleLinkItem<T> temp = new DoubleLinkItem<T>(null, item, null);
if (IsEmpty())
{
this.head = temp;
return;
}
DoubleLinkItem<T> tempItem = GetListItem(this.GetLength() - 1);
tempItem.Next = temp;
}
/// <summary>
/// 在雙向鏈表指定的位置插入一個新項
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
if (index < 0)
throw new Exception("插入位置不能小於0");
if (index > this.GetLength() + 1)
throw new Exception("插入位置超出鏈表長度");
if (index == 0)
{
DoubleLinkItem<T> temp = head;
this.head = new DoubleLinkItem<T>(null, item, temp);
return;
}
if (index == GetLength())
{
DoubleLinkItem<T> temp = GetListItem(index - 1);
temp.Next = new DoubleLinkItem<T>(temp, item, null);
return;
}
DoubleLinkItem<T> tempLast = GetListItem(index - 1);
DoubleLinkItem<T> tempNext = GetListItem(index);
tempLast.Next = new DoubleLinkItem<T>(tempLast, item, tempNext);
}
/// <summary>
/// 刪除指定位置的雙向鏈表項
/// </summary>
/// <param name="index"></param>
public void Delete(int index)
{
if (index < 0)
throw new Exception("刪除位置不能小於0");
if (index > this.GetLength() - 1)
throw new Exception("插入位置超出鏈表長度");
if (index == 0)
{
this.head = this.head.Next;
if (!IsEmpty())
this.head.Last = null;
return;
}
if (index == this.GetLength() - 1)
{
DoubleLinkItem<T> temp = GetListItem(index);
temp.Last.Next = null;
return;
}
DoubleLinkItem<T> tempItem = GetListItem(index);
DoubleLinkItem<T> tempLast = tempItem.Last;
DoubleLinkItem<T> tempNext = tempItem.Next;
tempLast.Next = tempNext;
tempNext.Last = tempLast;
}
/// <summary>
/// 獲取指定位置的雙向鏈表項目，頭項從0開始表示
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetItem(int index)
{
return GetListItem(index).Data;
}
/// <summary>
/// 獲取指定位置的雙向鏈表項目，頭項從0開始
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public DoubleLinkItem<T> GetListItem(int index)
{
if (index < 0)
throw new Exception("索引不能小於0");
if (index > this.GetLength() - 1)
throw new Exception("索引超出列表總長度");
DoubleLinkItem<T> temp = head;
for (int i = 0; i < index; i++)
{
temp = temp.Next;
}
return temp;
}
/// <summary>
/// 根據給定的鏈表項的值查找該項處於鏈表哪個位置
/// 當其中有相同項時，默認返回排在前面的項
/// </summary>
/// <param name="value">子項的值</param>
/// <returns></returns>
public int Locate(T value)
{
if (!IsEmpty())
{
if (head.Data.Equals(value))
return 0;
DoubleLinkItem<T> temp = head;
int i = 1;
while (temp.Next != null)
{
temp = temp.Next;
if (temp.Data.Equals(value))
return i;
i++;
}
}
return -1;
}
}
/// <summary>
/// 雙向鏈表子項類
/// </summary>
/// <typeparam name="T"></typeparam>
class DoubleLinkItem<T>
{
private DoubleLinkItem<T> last;
private DoubleLinkItem<T> next;
private T data;
public DoubleLinkItem<T> Last
{
set { last = value; }
get { return last; }
}
public DoubleLinkItem<T> Next
{
get { return next; }
set { next = value; }
}
public T Data
{
get { return data; }
set { data = value; }
}
/// <summary>
/// 構造函數，表示構造鏈表的中間子項，子項的前驅和後驅均不為空
/// 如果需要構造頭項或尾項，只需要將相應的前驅和後驅設置為空即可
/// </summary>
/// <param name="last">前驅</param>
/// <param name="data">子項數據</param>
/// <param name="next">後驅</param>
public DoubleLinkItem(DoubleLinkItem<T> last, T data, DoubleLinkItem<T> next)
{
this.last = last;
this.data = data;
this.next = next;
}
}
}
