链表&LRU

时间:2021-11-20 00:59:52

简介

链表就是链式存储数据的一种数据结构。双向链表每个数据存储都包含他的前后数据节点的位置信息(索引/指针)。

   class DSChain<T>
{
//使用栈来进行废弃空间回收
private DSStack<int> _recycle; //数据需要三个数据来存储内容,分别存储前后节点索引和数据本身
private int[] _prev;
private T[] _ds;
private int[] _next; //链表头尾的索引,跟踪表尾主要方便LRU使用
private int _head;
private int _tail; public DSChain(int length)
{
_head = -1;
_tail = -1;
_prev = new int[length];
_ds = new T[length];
_next = new int[length]; _recycle = new DSStack<int>(length);
//将所有可用空间压入栈,也可改良当顺序空间耗尽后再读取栈中记录的回收空间
for (int i = 0; i < length; i++)
{
_recycle.Push(i);
}
} //搜索数据,返回所在索引
int Search(T data)
{
if (_head == -1) return -1;
int index = _head;
while (!_ds[index].Equals(data))
{
index = _next[index];
if (index == -1) return -1;
}
return index;
} public bool Insert(T data)
{
int index;
if (!_recycle.Pop(out index)) return false;
if (_head == -1)
{
_prev[index] = -1;
_ds[index] = data;
_next[index] = -1;
_tail = index;
}
else
{
_prev[index] = -1;
_ds[index] = data;
_next[index] = _head;
_prev[_head] = index;
}
_head = index;
return true;
} public bool Delete(T data)
{
int index = Search(data);
if (index == -1) return false; if (_prev[index] != -1) _next[_prev[index]] = _next[index];
else _head = _next[index]; if (_next[index] != -1) _prev[_next[index]] = _prev[index];
else _tail = _prev[index]; _recycle.Push(index);
return true;
} //LRU
public bool DeleteLast()
{
int index = _tail;
if (index == -1) return false;
_tail = _prev[index];
_next[_prev[index]] = -1;
_recycle.Push(index);
return true;
} //LRU访问方法,读取数据的同时调整数据在链表中位置
//链表这种数据结构实现LRU非常方便
public bool LRUAccess(T data)
{
int index = Search(data);
if (index == -1) return false;
if (_head == index) return true;
if (_tail == index) _tail = _prev[index]; _next[_prev[index]] = _next[index];
if (_next[index] != -1) _prev[_next[index]] = _prev[index]; _prev[index] = -1;
_next[index] = _head;
_prev[_head] = index;
_head = index;
return true;
}
}