Unity用的双向链表

LinkList.cs

using UnityEngine;

//双向链表结点类，采用泛型
public class Node<T>
{
    private T data; //数据域，当前结点的数据
    private Node<T> prev; //引用域，即上一结点
    private Node<T> next; //引用域，即下一结点

    //构造器：数据域+引用域，普通结点
    public Node(T item, Node<T> n)
    {
        data = item;
        next = n;
    }
    public Node(Node<T> p, T item)
    {
        prev = p;
        data = item;
    }
    public Node(Node<T> p, T item, Node<T> n)
    {
        prev = p;
        data = item;
        next = n;
    }

    //构造器：引用域，头结点
    public Node(Node<T> n)
    {
        next = n;
    }

    //构造器：数据域，尾结点
    public Node(T val)
    {
        prev = null;
        data = val;
        next = null;
    }

    //构造器：无参数
    public Node()
    {
        prev = null;
        data = default(T);
        next = null;
    }

    //数据域属性
    public T Data
    {
        get
        {
            return data;
        }
        set
        {
            data = value;
        }
    }

    //引用域属性
    public Node<T> Next
    {
        get
        {
            return next;
        }
        set
        {
            next = value;
        }
    }
    public Node<T> Prev
    {
        get
        {
            return prev;
        }
        set
        {
            prev = value;
        }
    }
}

//链表类，包含链表定义及基本操作方法
public class LinkList<T>
{
    private Node<T> head; //链表的头结点
    private Node<T> tail; //链表的尾结点
    private Node<T> temp; //链表的缓存结点

    //头结点属性
    public Node<T> Head
    {
        get
        {
            return head;
        }
        set
        {
            head = value;
        }
    }

    //头结点属性
    public Node<T> Tail
    {
        get
        {
            return tail;
        }
        set
        {
            tail = value;
        }
    }

    //缓存结点属性
    public Node<T> Temp
    {
        get
        {
            if(temp == null){
                return head;
            }
            return temp;
        }
        set
        {
            temp = value;
        }
    }

    //构造器
    public LinkList()
    {
        head = null;
        tail = null;
        temp = head;
    }

    //求链表的长度
    public int GetLength()
    {
        Node<T> p = head;
        int len = 0;
        while (p != null)
        {
            ++len;
            p = p.Next;
        }
        return len;
    }

    //清空链表
    public void Clear()
    {
        head = null;
        tail = null;
    }

    //判断链表是否为空
    public bool IsEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    //在链表的末尾添加新元素
    public void Append(T item)
    {
        Node<T> q = new Node<T>(item);
        Node<T> p = new Node<T>();
        if (head == null)
        {
            head = q;
            tail = q;
            return;
        }
        tail.Next = q;
        q.Prev = tail;
        tail = tail.Next;
    }

    //在链表的第i个结点的位置前插入一个值为item的结点
    public void Insert(T item, int i)
    {
        int s = GetLength();
        if (IsEmpty() || i < 1 || i > GetLength())
        {
            Debug.Log("LinkedList is empty or Position is error!");
            return;
        }
        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = head;
            head.Prev = q;
            head = q;
            return;
        }
        if (i == s){
            Node<T> q = new Node<T>(item);
            Node<T> t = new Node<T>();
            t = tail.Prev;
            tail.Prev = q;
            q.Next = tail;
            q.Prev = t;
            t.Next = q;
            return;
        }
        Node<T> p = head;
        Node<T> r = new Node<T>();
        int j = 1;
        while (p.Next != null && j < i)
        {
            r = p;
            p = p.Next;
            ++j;
        }
        if (j == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p;
            p.Prev = q;
            r.Next = q;
            q.Prev = r;
        }
    }

    //在链表的第i个结点的位置后插入一个值为item的结点
    public void InsertPost(T item, int i)
    {
        int s = GetLength();
        if (IsEmpty() || i < 1 || i > s)
        {
            Debug.Log("LinkedList is empty or Position is error!");
            return;
        }
        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = head.Next;
            q.Prev = head;
            head.Next = q;
            return;
        }
        if(i == s){
            Node<T> q = new Node<T>(item);
            tail.Next = q;
            q.Prev = tail;
            tail = tail.Next;
            return;
        }
        Node<T> p = head;
        int j = 1;
        while (p != null && j < i)
        {
            p = p.Next;
            ++j;
        }
        if (j == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p.Next;
            q.Prev = p;
            p.Next = q;
            p = p.Next;
            q = q.Next;
            q.Prev = p;
        }
    }

    //删除链表的第i个结点
    public T Delete(int i)
    {
        int s = GetLength();
        if (IsEmpty() || i < 0 || i > s)
        {
            Debug.Log("LinkedList is empty or Position is error!");
            return default(T);
        }
        Node<T> q = new Node<T>();
        if (i == 1)
        {
            q = head;
            head = head.Next;
            head.Prev = null;
            q.Next = null;
            return q.Data;
        }
        if (i == s){
            q = tail;
            tail = tail.Prev;
            tail.Next = null;
            q.Prev = null;
            return q.Data;
        }
        Node<T> p = head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            ++j;
            q = p;
            p = p.Next;
        }
        if (j == i)
        {
            Node<T> r = new Node<T>();
            q.Next = p.Next;
            p.Prev = null;
            p.Next = null;
            r = q.Next;
            r.Prev = q;
            return p.Data;
        }
        else
        {
            Debug.Log("The " + i + "th node is not exist!");
            return default(T);
        }
    }

    //获得链表的第i个数据元素
    public T GetElem(int i)
    {
        if (IsEmpty() || i < 0)
        {
            Debug.Log("LinkedList is empty or position is error! ");
            return default(T);
        }
        Node<T> p = new Node<T>();
        p = head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            ++j;
            p = p.Next;
        }
        if (j == i)
        {
            return p.Data;
        }
        else
        {
            Debug.Log("The " + i + "th node is not exist!");
            return default(T);
        }
    }

    //在链表中查找值为value的结点
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Debug.Log("LinkedList is Empty!");
            return -1;
        }
        Node<T> p = new Node<T>();
        p = head;
        int i = 1;
        while (!p.Data.Equals(value) && p.Next != null)
        {
            p = p.Next;
            ++i;
        }
        return i;
    }

    //显示链表，只能用于String形式的链表
    public void Display()
    {
        Node<T> p = new Node<T>();
        p = this.head;
        while (p != null)
        {
            Debug.Log(p.Data + " ");
            p = p.Next;
        }
    }
    public void DisplayR()
    {
        Node<T> p = new Node<T>();
        p = this.tail;
        while (p != null)
        {
            Debug.Log(p.Data + " ");
            p = p.Prev;
        }
    }
}