簡介

鏈表就是鏈式存儲數據的一種數據結構。雙向鏈表每個數據存儲都包含他的前后數據節點的位置信息（索引/指針）。

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;}//LRUpublic 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;}}

轉載于:https://www.cnblogs.com/zhang740/p/3785711.html

總結

以上是生活随笔為你收集整理的链表LRU的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。