链表

什么是链表？

链表又叫单链表，是链式存储结构的线性表。在内存中是散乱随机存储的。
链表中的数据由结点表示，由两部分组成：

• 数据本身，所在区域称为数据域
• 指向直接后继元素的指针（C#中为引用），所在区域称为指针域

头指针、头结点、首元结点是什么？

一个链表光有结点还不完整。
一个完整的链表由以下几部分构成：

• 头指针：永远指向链表第一个位置。用于指明链表的位置，便于找到链表并使用链表中的数据。
• 结点：
  • 头结点：没有数据的空结点，作为链表的第一个结点。不是必须有。
  • 首元结点：链表中第一个存有数据的结点。
  • 其他结点：链表中除以上结点以外的其他的结点。

链表中有头结点时，头指针指向头结点。没有头结点时，头指针指向首元结点。

链表及其变种

• 按照结点方向：单链表、双向链表
• 按照是否循环：普通链表、循环链表
• 按照是否带头结点：有头结点的、没有头结点的
• 按照头结点位置：头结点在链表首、头结点在链表尾

链表的实现

这里以无头结点普通单链表为例。
普通单遍历链表有一个限制：只通过头指针开始遍历

结点

首先实现链表的结点

public class Node<T>
{
    public T Elem;
    public Node<T> Next;

    public Node()
    {
    }

    public Node(T elem)
    {
        Elem = elem;
    }

    public Node(T elem, Node<T> next)
    {
        Elem = elem;
        Next = next;
    }

    public override string ToString()
    {
        return Elem.ToString();
    }
}

初始化

链表的初始化

private Node<T> Head;
private int count;

public int Count { get { return count; } }
public bool IsEmpty { get { return count <= 0; } }

public SingleLinkList()
{
    Head = null;
    count = 0;
}

插入

/// <summary>
/// 插入
/// </summary>
/// <param name="index"></param>
/// <param name="elem"></param>
public void Insert(int index, T elem)
{
    if (index < 0 || index > count)
    {
        throw new ArgumentException("非法索引");
    }
    if (index == 0)
    {
        Head = new Node<T>(elem, Head);
    }
    else
    {
        Node<T> tmp = Head;
        for (int i = 0; i < index - 1; i++)
        {
            tmp = tmp.Next;
        }
        tmp.Next = new Node<T>(elem, tmp.Next);
    }
    count++;
}

/// <summary>
/// 从头部插入
/// </summary>
/// <param name="elem"></param>
public void AddFirst(T elem)
{
    Insert(0, elem);
}

/// <summary>
/// 从尾部插入
/// </summary>
/// <param name="elem"></param>
public void AddLast(T elem)
{
    Insert(count, elem);
}

移除

/// <summary>
/// 根据索引号移除
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T RemoveAt(int index)
{
    if (index < 0 || index >= count)
    {
        throw new ArgumentOutOfRangeException();
    }

    if (index == 0)
    {
        Node<T> node = Head;
        Head = Head.Next;
        count--;
        return node.Elem;
    }
    else
    {
        Node<T> tmp = Head;
        for (int i = 0; i < index - 1; i++)
        {
            tmp = tmp.Next;
        }
        Node<T> node = tmp.Next;
        tmp.Next = node.Next;
        count--;
        return node.Elem;
    }
}

/// <summary>
/// 根据索引号从头部移除
/// </summary>
/// <returns></returns>
public T RemoveFirst()
{
    return RemoveAt(0);
}

/// <summary>
/// 根据索引号从尾部移除
/// </summary>
/// <returns></returns>
public T RemoveLast()
{
    return RemoveAt(count - 1);
}

/// <summary>
/// 移除元素
/// </summary>
/// <param name="elem"></param>
public void Remove(T elem)
{
    if (Head == null)
    {
        return;
    }
    if (Head.Elem.Equals(elem))
    {
        Head = Head.Next;
        count--;
    }
    else
    {
        Node<T> cur = Head;
        Node<T> pre = null;
        while (cur != null)
        {
            if (cur.Elem.Equals(elem))
            {
                break;
            }
            pre = cur;
            cur = cur.Next;
        }

        if (cur != null)
        {
            pre.Next = cur.Next;
            count--;
        }
    }
}

赋值

/// <summary>
/// 根据索引号设置元素
/// </summary>
/// <param name="index"></param>
/// <param name="elem"></param>
public void Set(int index, T elem)
{
    if (index < 0 || index >= count)
    {
        throw new ArgumentOutOfRangeException();
    }
    Node<T> tmp = Head;
    for (int i = 0; i < index; i++)
    {
        tmp = tmp.Next;
    }
    tmp.Elem = elem;
}

查询

/// <summary>
/// 获取链表中的元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T Get(int index)
{
    if (index < 0 || index >= count)
    {
        throw new ArgumentOutOfRangeException();
    }
    Node<T> tmp = Head;
    for (int i = 0; i < index; i++)
    {
        tmp = tmp.Next;
    }
    return tmp.Elem;
}

/// <summary>
/// 获取第一个元素
/// </summary>
/// <returns></returns>
public T GetFirst()
{
    return Get(0);
}

/// <summary>
/// 获取最后一个元素
/// </summary>
/// <returns></returns>
public T GetLast()
{
    return Get(count - 1);
}

/// <summary>
/// 是否包含某个元素
/// </summary>
/// <param name="elem"></param>
/// <returns></returns>
public bool Contains(T elem)
{
    for (Node<T> node = Head; node != null; node = node.Next)
    {
        if (node.Elem.Equals(elem))
        {
            return true;
        }
    }
    return false;
}

其他

链表的反转，有4中实现方式：

• 迭代反转法
• 递归反转法
• 就地逆置法
• 头插法

这里使用迭代法实现了一遍

/// <summary>
/// 链表反转，迭代反转法
/// </summary>
public void Reverse()
{
    if (Head == null || Head.Next == null)
    {
        return;
    }

    Node<T> begin = null;
    Node<T> mid = Head;
    Node<T> end = mid.Next;
    while (true)
    {
        mid.Next = begin;

        if (end == null)
        {
            break;
        }

        begin = mid;
        mid = end;
        end = end.Next;
    }

    Head = mid;
}