在單鏈表中，我們需要在內部有一個頭節點，我們可以通過這個頭節點找到其他的節點，相當于一個線索。
縱觀順序結構的線性表和單鏈表的實現，難點基本上都在于添加和刪除操作。基于數組的線性表中，數組的索引就相當于是線性表的序號，但在單鏈表中，我們沒有序號這個東西，所以在添加和刪除操作中，我們需要先找到指定的元素，然后才能繼續進行操作。在插入操作中，我們需要同時保存有當前節點的前一個節點和當前的節點，因為當前要插入的節點要放在前一個節點的Next引用域，而當前節點要放在要插入節點的next域。刪除節點與此相似。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
class LinkList<T> : IListDS<T>
{
class Node<T>
{
private T data;
/// <summary>
/// 數據域
/// </summary>
public T Data
{
get { return data; }
set { data = value; }
}
private Node<T> next;
/// <summary>
/// 引用域
/// </summary>
public Node<T> Next
{
get { return next; }
set { next = value; }
}
//頭結點構造函數
public Node(Node<T> node)
: this(default(T), node)
{
}
//普通結點構造函數
public Node(T data, Node<T> node)
{
this.Data = data;
this.Next = node;
}
/// <summary>
/// 空構造函數
/// </summary>
public Node()
: this(default(T), null)
{
}
//尾結點構造函數
public Node(T data)
: this(data, null)
{
}
}
private Node<T> Head;
public LinkList()
{
}
public int Lenth
{
get { return this.GetLength(); }
}
public LinkList(T[] t)
{
this.Head = new Node<T>(t[0]);
Node<T> Last;
Last = Head;
for (int i = 1; i < t.Length; i++)
{
//尾插入法
Last.Next = new Node<T>(t[i]);
Last = Last.Next;
}
}
public States Append(T item)
{
//(1)頭結點沒有
if (Head==null)
{
Head = new Node<T>(item);
}
//(2)正常的插入情況
Node<T> Last;
Last=Head;
//遍歷到最后一個結點，在最后一個結點附加上
while (null!=Last.Next)
{
Last = Last.Next;
}
Last.Next = new Node<T>(item);
return States.Success;
}
public void Clear()
{
this.Head = null;
}
public T Delete(int index, out States states)
{
bool isIndexTrue = index < 0 || index >= this.GetLength();
if (IsEmpty() == true || isIndexTrue)
{
states = States.Fail;
return default(T);
}
//找到指定的結點
Node<T> Current = Head;
Node<T> Previous = Head;
int Count = 0;
while (Count != index && Current.Next != null)
{
Previous = Current;
Current = Current.Next;
Count++;
}
T ValueToDel = Current.Data;
//是否是頭結點
if (Count == 0)
{
Head = Current.Next;
}
//是否是普通的結點
if (Count != 0 && Current.Next != null)
{
Previous.Next = Current.Next;
}
//是否是最后一個結點
if (Count != 0 && Current.Next == null)
{
Previous.Next = null;
}
//刪除結點
states = States.Success;
return ValueToDel;
}
public T GetElem(int i)
{
if (i < 0 || i >= this.GetLength())
{
return default(T);
}
if (IsEmpty() == true)
{
return default(T);
}
Node<T> Last = Head;
int Count = 0;
while (Count != i && Last.Next != null)
{
Last = Last.Next;
Count++;
}
return Last.Data;
}
public int GetLength()
{
if (Head==null)
{
return 0;
}
Node<T> Last;
Last = Head;
int Count=0;
while (Last.Next!=null)
{
Last = Last.Next;
Count++;
}
return ++Count;
//throw new NotImplementedException();
}
public States Insert(T item, int index)
{
bool isIndexTrue = index < 0 || index > this.GetLength();
if (isIndexTrue)
{
return States.Fail;
}
//如果鏈表為空
if (IsEmpty() == true )
{
Head.Data = item;
}
//如果是第一個結點
if (index==0)
{
Node<T> node = new Node<T>(item);
node.Next = Head;
Head = node;
}
//如果是普通的結點
Node<T> Previous = Head;
// Node<T> Previous = Head;
int Count = 0;
while (Count != index-1 && Previous.Next != null)
{
// Previous = Current;
Previous = Previous.Next;
Count++;
}
if (Count == index-1)
{
Node<T> node=new Node<T>(item);
node.Next = Previous.Next;
Previous.Next = node;
}
//如果是最后一個結點
if (this.GetLength()==index)
{
Previous.Next = new Node<T>(item);
}
return States.Success;
}
public bool IsEmpty()
{
return Head == null ? true : false;
}
public int Locate(T value, out States states)
{
if (IsEmpty() == true)
{
states = States.Fail;
return 0;
}
Node<T> Last = Head;
int Count = 0;
while (Last.Next != null &&( !value.Equals(Last.Data)))
{
Last = Last.Next;
Count++;
}
states = States.Success;
return Count;
}
}
}
文章列表
留言列表
