为什么使用双向链表

如果一个资源被频繁调用，我们希望它在链表的顶部，而不频繁调用的资源会慢慢地沉向底部，当我们想要释放资源时，位于底部的资源会被优先释放。

当然我们也可以在代码中指定当前资源是否常用，指定当前资源被卸载时是否是完全卸载。

双向链表类

我们的双向链表类配合对象池进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
public class DoubleLinkedListNode<T> where T : class,new()
{
    public DoubleLinkedListNode<T> prev, next;//前一个节点和后一个节点
    public T item = null;
}
public class DoubleLinkedList<T> where T : class, new()
{
    public DoubleLinkedListNode<T> Head,Tail = null;//表头和表尾
    //双向链表结构类对象池
    protected ClassObjectPool<DoubleLinkedListNode<T>> m_DoubleLinkedNodePool = 
        ObjectPoolManager.Instance.GetOrCreatClassPool<DoubleLinkedListNode<T>>(500);

    protected int m_Count = 0;
    public int Count
    {
        get { return m_Count; }
    }
    /// <summary>
    /// 添加一个节点到头部
    /// </summary>
    public DoubleLinkedListNode<T> AddToHeader(T item)
    {
        DoubleLinkedListNode<T> pList = m_DoubleLinkedNodePool.Spawn(true);
        pList.next = null;
        pList.prev = null;
        pList.item = item;
        return AddToHeader(pList);
    }
    /// <summary>
    /// 添加一个节点到头部
    /// </summary>
    public DoubleLinkedListNode<T> AddToHeader(DoubleLinkedListNode<T> pNode)
    {
        if (pNode == null)
            return null;
        pNode.prev = null;
        if (Head == null)
        {
            Head = Tail = pNode;
        }
        else
        {
            pNode.next = Head;
            Head.prev = pNode;
            Head = pNode;
        }
        m_Count++;
        return Head;
    }
    /// <summary>
    /// 添加一个节点到尾部
    /// </summary>
    public DoubleLinkedListNode<T> AddToTail(T item)
    {
        DoubleLinkedListNode<T> pList = m_DoubleLinkedNodePool.Spawn(true);
        pList.next = null;
        pList.prev = null;
        pList.item = item;
        return AddToTail(pList);
    }
    /// <summary>
    /// 添加一个节点到尾部
    /// </summary>
    public DoubleLinkedListNode<T> AddToTail(DoubleLinkedListNode<T> pNode)
    {
        if(pNode == null) return null;
        pNode.next = null;
        if(Tail == null)
        {
            Head= Tail = pNode;
        }
        else
        {
            pNode.prev = Tail;
            Tail.next = pNode;
            Tail= pNode;
        }
        m_Count++;
        return Tail;
    }
    /// <summary>
    /// 移除某个节点，注意节点的移除不是将节点置空，而是返回对象池
    /// </summary>
    public void RemoveNode(DoubleLinkedListNode<T> pNode)
    {
        if(pNode == null) return;
        if(pNode == Head)
        {
            Head = pNode.next;
        }
        if (pNode == Tail)
        {
            Tail = pNode.prev;
        }
        if(pNode.prev != null)
        {
            pNode.prev.next = pNode.next;
        }
        if(pNode.next != null)
        {
            pNode.next.prev = pNode.prev;
        }
        pNode.next = null;
        pNode.prev= null;
        pNode.item = null;
        m_DoubleLinkedNodePool.Recycle(pNode);
        m_Count--;
    }
    /// <summary>
    /// 把某个节点移动到头部
    /// </summary>
    public void MoveToHead(DoubleLinkedListNode<T> pNode)
    {
        if(pNode == null || pNode == Head) return;
        //如果此节点之前被移除了，就会出现这种情况
        if(pNode.prev == null && pNode.next == null)
        {
            return;
        }
        if(pNode ==  Tail)
        {
            Tail = pNode.prev;//在这里指定
        }
        if(pNode.prev != null)
        {
            pNode.prev.next = pNode.next;
        }
        if(pNode.next != null)
        {
            pNode.next.prev = pNode.prev;
        }
        pNode.prev = null;//在这里Tail可能置空
        pNode.next = Head;
        Head.prev = pNode;
        Head = pNode;
        //如果链表中只有两个Node，到这里Tail可能置空，所以需要这样
        if (Tail == null)
        {
            Tail = Head;
        }
    }
}

封装双向链表

我们再把双向链表进行一次封装，引入一个字典，用于更方便快速地查找双向链表里面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
public class CMapList<T> where T : class, new()
{
    DoubleLinkedList<T> m_DLink = new DoubleLinkedList<T>();
    //使用一个字典将t和它对应的双向链表的Node缓存起来
    Dictionary<T,DoubleLinkedListNode<T>> m_FindMap = new Dictionary<T, DoubleLinkedListNode<T>>();
    ~CMapList()//析构函数
    {
        Clear();
    }
    /// <summary>
    /// 清空双向链表
    /// </summary>
    public void Clear()
    {
        while (m_DLink.Tail != null)
        {
            Remove(m_DLink.Tail.item);
        }
    }
    /// <summary>
    /// 插入一个节点到表头
    /// </summary>
    public void InsertToHead(T t)
    {
        DoubleLinkedListNode<T> node = null;
        if (m_FindMap.TryGetValue(t, out node) && node != null)
        {
            m_DLink.AddToHeader(node);
            return;
        }
        m_DLink.AddToHeader(t);
        m_FindMap.Add(t, m_DLink.Head);
    }
    /// <summary>
    /// 从表尾删除一个节点
    /// </summary>
    public void Pop()
    {
        if (m_DLink.Tail != null)
        {
            Remove(m_DLink.Tail.item);
        }
    }
    /// <summary>
    /// 删除某个节点
    /// </summary>
    public void Remove(T t)
    {
        DoubleLinkedListNode<T> node = null;
        if(!m_FindMap.TryGetValue(t,out node) || node == null)
        {
            return;
        }
        m_DLink.RemoveNode(node);
        m_FindMap.Remove(t);
    }
    /// <summary>
    /// 获取到尾部节点
    /// </summary>
    public T Back()
    {
        return m_DLink.Tail == null? null: m_DLink.Tail.item;
    }
    /// <summary>
    /// 返回节点个数
    /// </summary>
    public int Size()
    {
        return m_FindMap.Count;
    }
    /// <summary>
    /// 是否存在该节点
    /// </summary>
    public bool Find(T t)
    {
        DoubleLinkedListNode<T> node = null;
        if (!m_FindMap.TryGetValue(t, out node) || node == null)
        {
            return false;
        }
        return true;
    }
    /// <summary>
    /// 把节点移动到头部
    /// </summary>
    public bool Refresh(T t)
    {
        DoubleLinkedListNode<T> node = null;
        if (!m_FindMap.TryGetValue(t, out node) || node == null)
        {
            return false;
        }
        m_DLink.MoveToHead(node);
        return true;
    }
}