链表

链表定义:一种递归的数据结构, 它是在集合类的抽象数据,它或者为空, 或者是指向一个节点 (node) 的引用, 该结点含有一个泛型的元素和一个指向另一条链表的引用。

单向链表:

    public class LinkList<T> : IEnumerable
    {
        public Node First { get => _first; set { _first = value; } }
        public Node Last { get => _last; set { _last = value; } }
        public bool isEmpty() { return _first == null; }

        private Node _first;
        private Node _last;
        private int N;
         
        // 节点的抽象数据类型
        public class Node
        {
            public T val;
            public Node next;

            public Node(T val) { this.val = val; }
        }

        public void AddFirst(T val)
        {
            // it doesn't matter whether the first is null
            Node oldFirst = _first;
            _first = new Node(val);
            _first.next = oldFirst;
            N++;
            if (N == 1) { _last = _first; }
        }

        public void AddLast(T val)
        {
            // it doesn't matter whether the last is null
            Node oldLast = _last;
            _last = new Node(val);
            _last.next = null;
            N++;
            if (N == 1) { _first = _last; }
            else oldLast.next = _last;
        }

        // make the class iterable
        public IEnumerator GetEnumerator()
        {
            Node current = _first;

            while (current != null)
            {
                yield return current.val;
                current = current.next;
            }
        }
    

循环链表:

  public class RecycleLinkList<Tval> : IEnumerable
    {
        public class Node
        {
            public Tval val;
            public Node next;
            public Node(Tval val) { this.val = val; }
        }

        private Node _first;
        private Node _last;
        private int _n;

        public Node First { set => _first = value; get => _first; }
        public Node Last { set => _last = value; get => _last; }
        public bool IsEmpty() { return _first == null; }
        public int Size() { return _n; }

        public void Add(Tval val)
        {
            Node oldLast = _last;
            _last = new Node(val);

            if (IsEmpty())
            {
                _first = _last;
            }
            else
            {
                oldLast.next = _last;
            }

            _n++;
            // 与单向链表唯一的不同,多了下面这行代码
            // last.next = null;
            _last.next = _first;
        }

        public IEnumerator GetEnumerator()
        {
            Node current = _first;

            while (current != null)
            {
                yield return current.val;
                current = current.next;
            }
        }
    }

双向循环链表:

可实现任意插入和删除操作, 与单向链表相比多了一个向前的指向。

    public class DoubleRecycleLinkedList<Tval>
    {
        public class Node
        {
            public Tval Val { set; get; }
            public Node Next { set; get; }
            public Node Prev { set; get; }
            public Node(Tval val, Node prev, Node next)
            {
                this.Val = val;
                this.Prev = prev;
                this.Next = next;
            }
        }

        private Node _first;
        private Node _last;
        private int _size;
        public DoubleRecycleLinkedList()
        {
            _first = new Node(default(Tval), null, null);
            _first.Prev = _first;
            _first.Next = _first;
            _size = 0;
        }

        public int Size() => _size;
        public bool IsEmpty() => _size == 0;

        // search by index
        private Node GetNode(int index)
        {
            if (index < 0 || index >= _size)
            {
                throw new IndexOutOfRangeException("the index overflow or the linkedList is null");
            }
        
            // choose lookup mehtod by compare the index with _size/2 (save a lot of times)
            // forward lookup
            if (index < _size/2)  
            {
                Node current = _first.Next;
                for (int i = 0; i < index; i++)
                {
                    current = current.Next;
                }
                return current;
            }

            // reverse lookup
            Node rnode = _first.Prev;
            int rindex = _size - index - 1;
            for (int i = 0; i < rindex; i++)
            {
                rnode = rnode.Prev;
            }
            return rnode;
        }

        public Tval Get(int index) => GetNode(index).Val;

        // add node before the index
        public void InsertPrev(int index, Tval t)
        {
            if (_size < 1 || index >= _size)
            {
                throw new Exception("index overflow");
            }
            if (index == 0)
            {
                InsetAfter(_size, t);
            }
            else
            {
                Node inode = GetNode(index);
                Node tnode = new Node(t, inode.Prev, inode);
                inode.Prev.Next = tnode;
                _size++;
            }
        }

        // add node after the index
        public void InsetAfter(int index, Tval t)
        {
            Node inode;
            if (index == 0) { inode = _first; }
            else
            {
                // 此处代码可能有误, 无需用 index - 1 , 直接用index 即可 
                //index = index - 1;
                if (index < 0)
                {
                    throw new IndexOutOfRangeException("位置不存在");
                }
                inode = GetNode(index);
            }

            Node tnode = new Node(t, inode, inode.Next);
            inode.Next.Prev = tnode;
            inode.Next = tnode;
            _size++;
        }

        public void Del(int index)
        {
            Node inode = GetNode(index);
            inode.Prev.Next = inode.Next;
            inode.Next.Prev = inode.Prev;
            _size--;
        }

        public void ShowAll()
        {
            for (int i = 0; i < _size; i++)
            {
                Console.WriteLine(Get(i));
            }
        }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

python的迭代器和生成器

迭代是数据处理的基础,迭代可以理解为是一种惰性求值。在python里迭代器和生成器是一回事,使用的是yield关键字。

8210
来自专栏程序猿DD

你真的了解lambda吗?一文让你明白lambda用法与源码分析

本文链接: http://www.cmlanche.com/2018/07/22/lambda用法与源码分析/

14020
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常—— Arrays工具类的使用

这个类在日常的开发中,还是非常常用的。今天就总结一下Arrays工具类的常用方法。最常用的就是asList,sort,toStream,equals,copy...

19770
来自专栏陈树义

Java集合常见面试题集锦

1、介绍Collection框架的结构 集合是Java中的一个非常重要的一个知识点,主要分为List、Set、Map、Queue三大数据结构。它们在Java中的...

44150
来自专栏程序猿DD

第二章 正则表达式位置匹配攻略

第二章 正则表达式位置匹配攻略 正则表达式是匹配模式,要么匹配字符,要么匹配位置。请记住这句话。 然而大部分人学习正则时,对于匹配位置的重视程度没有那么高。 本...

238100
来自专栏向治洪

Kotlin之基本语法

在今年Google IO大会上Google已经明确kotlin作为为Android第一官方语言的地位。我相信Google的决意,就像当初毫不犹豫的抛弃eclip...

23580
来自专栏Golang语言社区

Go 语言数据类型

在 Go 编程语言中,数据类型用于声明函数和变量。 数据类型的出现是为了把数据分成所需内存大小不同的数据,编程的时候需要用大数据的时候才需要申请大内存,就可以充...

32770
来自专栏向治洪

Kotlin之基本语法

在今年Google IO大会上Google已经明确kotlin作为为Android第一官方语言的地位。我相信Google的决意,就像当初毫不犹豫的抛弃eclip...

26870
来自专栏赵俊的Java专栏

删除元素

10110
来自专栏阮一峰的网络日志

Ramda 函数库参考教程

学习函数式编程的过程中,我接触到了 Ramda.js。 我发现,这是一个很重要的库,提供了许多有用的方法,每个 JavaScript 程序员都应该掌握这个工具。...

93980

扫码关注云+社区

领取腾讯云代金券