链表&LRU

简介

链表就是链式存储数据的一种数据结构。双向链表每个数据存储都包含他的前后数据节点的位置信息（索引/指针）。
   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;

        }

    }
巴特西

链表&LRU

简介

最新文章

热门文章
