链表定义:一种递归的数据结构, 它是在集合类的抽象数据,它或者为空, 或者是指向一个节点 (node) 的引用, 该结点含有一个泛型的元素和一个指向另一条链表的引用。
单向链表:
public class LinkList<T> : IEnumerable
{
public Node First { get => _first; set { _first = value; } }
public Node Last { get => _last; set { _last = value; } }
public bool isEmpty() { return _first == null; }
private Node _first;
private Node _last;
private int N;
// 节点的抽象数据类型
public class Node
{
public T val;
public Node next;
public Node(T val) { this.val = val; }
}
public void AddFirst(T val)
{
// it doesn't matter whether the first is null
Node oldFirst = _first;
_first = new Node(val);
_first.next = oldFirst;
N++;
if (N == 1) { _last = _first; }
}
public void AddLast(T val)
{
// it doesn't matter whether the last is null
Node oldLast = _last;
_last = new Node(val);
_last.next = null;
N++;
if (N == 1) { _first = _last; }
else oldLast.next = _last;
}
// make the class iterable
public IEnumerator GetEnumerator()
{
Node current = _first;
while (current != null)
{
yield return current.val;
current = current.next;
}
}
循环链表:
public class RecycleLinkList<Tval> : IEnumerable
{
public class Node
{
public Tval val;
public Node next;
public Node(Tval val) { this.val = val; }
}
private Node _first;
private Node _last;
private int _n;
public Node First { set => _first = value; get => _first; }
public Node Last { set => _last = value; get => _last; }
public bool IsEmpty() { return _first == null; }
public int Size() { return _n; }
public void Add(Tval val)
{
Node oldLast = _last;
_last = new Node(val);
if (IsEmpty())
{
_first = _last;
}
else
{
oldLast.next = _last;
}
_n++;
// 与单向链表唯一的不同,多了下面这行代码
// last.next = null;
_last.next = _first;
}
public IEnumerator GetEnumerator()
{
Node current = _first;
while (current != null)
{
yield return current.val;
current = current.next;
}
}
}
双向循环链表:
可实现任意插入和删除操作, 与单向链表相比多了一个向前的指向。
public class DoubleRecycleLinkedList<Tval>
{
public class Node
{
public Tval Val { set; get; }
public Node Next { set; get; }
public Node Prev { set; get; }
public Node(Tval val, Node prev, Node next)
{
this.Val = val;
this.Prev = prev;
this.Next = next;
}
}
private Node _first;
private Node _last;
private int _size;
public DoubleRecycleLinkedList()
{
_first = new Node(default(Tval), null, null);
_first.Prev = _first;
_first.Next = _first;
_size = 0;
}
public int Size() => _size;
public bool IsEmpty() => _size == 0;
// search by index
private Node GetNode(int index)
{
if (index < 0 || index >= _size)
{
throw new IndexOutOfRangeException("the index overflow or the linkedList is null");
}
// choose lookup mehtod by compare the index with _size/2 (save a lot of times)
// forward lookup
if (index < _size/2)
{
Node current = _first.Next;
for (int i = 0; i < index; i++)
{
current = current.Next;
}
return current;
}
// reverse lookup
Node rnode = _first.Prev;
int rindex = _size - index - 1;
for (int i = 0; i < rindex; i++)
{
rnode = rnode.Prev;
}
return rnode;
}
public Tval Get(int index) => GetNode(index).Val;
// add node before the index
public void InsertPrev(int index, Tval t)
{
if (_size < 1 || index >= _size)
{
throw new Exception("index overflow");
}
if (index == 0)
{
InsetAfter(_size, t);
}
else
{
Node inode = GetNode(index);
Node tnode = new Node(t, inode.Prev, inode);
inode.Prev.Next = tnode;
_size++;
}
}
// add node after the index
public void InsetAfter(int index, Tval t)
{
Node inode;
if (index == 0) { inode = _first; }
else
{
// 此处代码可能有误, 无需用 index - 1 , 直接用index 即可
//index = index - 1;
if (index < 0)
{
throw new IndexOutOfRangeException("位置不存在");
}
inode = GetNode(index);
}
Node tnode = new Node(t, inode, inode.Next);
inode.Next.Prev = tnode;
inode.Next = tnode;
_size++;
}
public void Del(int index)
{
Node inode = GetNode(index);
inode.Prev.Next = inode.Next;
inode.Next.Prev = inode.Prev;
_size--;
}
public void ShowAll()
{
for (int i = 0; i < _size; i++)
{
Console.WriteLine(Get(i));
}
}