数据结构基础温故-1.线性表(中)

上一篇中,我们学习了线性表最基础的表现形式-顺序表,但是其存在一定缺点:必须占用一整块事先分配好的存储空间,在插入和删除操作上需要移动大量元素(即操作不方便),于是不受固定存储空间限制并且可以进行比较快捷地插入和删除操作的链表横空出世,所以我们就来复习一下链表。

一、单链表基础

1.1 单链表的节点结构

  在链表中,每个节点由两部分组成:数据域指针域

1.2 单链表的总体结构

  链表就是由N个节点链接而成的线性表,如果其中每个节点只包含一个指针域那么就称为单链表,如果含有两个指针域那么就称为双链表

PS:在线性表的链式存储结构中,为了便于插入和删除操作的实现,每个链表都带有一个头指针(或尾指针),通过头指针可以唯一标识该链表。从头指针所指向的节点出发,沿着节点的链可以访问到每个节点。

二、单链表实现

2.1 单链表节点的定义

    public class Node<T>
    {
        // 数据域
        public T Item { get; set; }
        // 指针域
        public Node<T> Next { get; set; }

        public Node()
        {
        }

        public Node(T item)
        {
            this.Item = item;
        }
    }

  此处定义Node类为单链表的节点,其中包括了一个数据域Item与一个指针域Next(指向后继节点的位置)。

2.2 单链表节点的新增

  ①默认在尾节点后插入新节点

        public void Add(T value)
        {
            Node<T> newNode = new Node<T>(value);
            if (this.head == null)
            {
                // 如果链表当前为空则置为头结点
                this.head = newNode;
            }
            else
            {
                Node<T> prevNode = this.GetNodeByIndex(this.count - 1);
                prevNode.Next = newNode;
            }

            this.count++;
        }    

  首先判断头结点是否为空,其次依次遍历各节点找到尾节点的前驱节点,然后更改前驱节点的Next指针指向新节点即可。

  ②指定在某个节点后插入新节点

        public void Insert(int index, T value)
        {
            Node<T> tempNode = null;
            if (index < 0 || index > this.count)
            {
                throw new ArgumentOutOfRangeException("index", "索引超出范围");
            }
            else if (index == 0)
            {
                if (this.head == null)
                {
                    tempNode = new Node<T>(value);
                    this.head = tempNode;
                }
                else
                {
                    tempNode = new Node<T>(value);
                    tempNode.Next = this.head;
                    this.head = tempNode;
                }
            }
            else
            {
                Node<T> prevNode = GetNodeByIndex(index - 1);
                tempNode = new Node<T>(value);
                tempNode.Next = prevNode.Next;
                prevNode.Next = tempNode;
            }

            this.count++;
        }

  这里需要判断是否是在第一个节点进行插入,如果是则再次判断头结点是否为空。

2.3 单链表节点的移除

        public void RemoveAt(int index)
        {
            if (index == 0)
            {
                this.head = this.head.Next;
            }
            else
            {
                Node<T> prevNode = GetNodeByIndex(index - 1);
                if (prevNode.Next == null)
                {
                    throw new ArgumentOutOfRangeException("index", "索引超出范围");
                }

                Node<T> deleteNode = prevNode.Next;
                prevNode.Next = deleteNode.Next;

                deleteNode = null;
            }

            this.count--;
        }

  移除某个节点只需将其前驱节点的Next指针指向要移除节点的后继节点即可。

  至此,关键部分的代码已介绍完毕,下面给出完整的单链表模拟实现代码:

/// <summary>
/// 单链表模拟实现
/// </summary>
public class MySingleLinkedList<T>
{
        private int count; // 字段:当前链表节点个数
        private Node<T> head; // 字段:当前链表的头结点

        // 属性:当前链表节点个数
        public int Count
        {
            get
            {
                return this.count;
            }
        }

        // 索引器
        public T this[int index]
        {
            get
            {
                return this.GetNodeByIndex(index).Item;
            }
            set
            {
                this.GetNodeByIndex(index).Item = value;
            }
        }

        public MySingleLinkedList()
        {
            this.count = 0;
            this.head = null;
        }

        // Method01:根据索引获取节点
        private Node<T> GetNodeByIndex(int index)
        {
            if (index < 0 || index >= this.count)
            {
                throw new ArgumentOutOfRangeException("index", "索引超出范围");
            }

            Node<T> tempNode = this.head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.Next;
            }

            return tempNode;
        }

        // Method02:在尾节点后插入新节点
        public void Add(T value)
        {
            Node<T> newNode = new Node<T>(value);
            if (this.head == null)
            {
                // 如果链表当前为空则置为头结点
                this.head = newNode;
            }
            else
            {
                Node<T> prevNode = this.GetNodeByIndex(this.count - 1);
                prevNode.Next = newNode;
            }

            this.count++;
        }

        // Method03:在指定位置插入新节点
        public void Insert(int index, T value)
        {
            Node<T> tempNode = null;
            if (index < 0 || index > this.count)
            {
                throw new ArgumentOutOfRangeException("index", "索引超出范围");
            }
            else if (index == 0)
            {
                if (this.head == null)
                {
                    tempNode = new Node<T>(value);
                    this.head = tempNode;
                }
                else
                {
                    tempNode = new Node<T>(value);
                    tempNode.Next = this.head;
                    this.head = tempNode;
                }
            }
            else
            {
                Node<T> prevNode = GetNodeByIndex(index - 1);
                tempNode = new Node<T>(value);
                tempNode.Next = prevNode.Next;
                prevNode.Next = tempNode;
            }

            this.count++;
        }

        // Method04:移除指定位置的节点
        public void RemoveAt(int index)
        {
            if (index == 0)
            {
                this.head = this.head.Next;
            }
            else
            {
                Node<T> prevNode = GetNodeByIndex(index - 1);
                if (prevNode.Next == null)
                {
                    throw new ArgumentOutOfRangeException("index", "索引超出范围");
                }

                Node<T> deleteNode = prevNode.Next;
                prevNode.Next = deleteNode.Next;

                deleteNode = null;
            }

            this.count--;
        }
    }
}

2.4 单链表的模拟实现简单测试

  这里针对模拟的单链表进行三个简单的测试:一是顺序插入4个节点;二是在指定的位置插入单个节点;三是移除指定位置的单个节点;测试代码如下所示:

    static void MySingleLinkedListTest()
    {
            MySingleLinkedList<int> linkedList = new MySingleLinkedList<int>();
            // Test1:顺序插入4个节点
            linkedList.Add(0);
            linkedList.Add(1);
            linkedList.Add(2);
            linkedList.Add(3);

            Console.WriteLine("The nodes in the linkedList:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            Console.WriteLine("----------------------------");

            // Test2.1:在索引为0(即第1个节点)的位置插入单个节点
            linkedList.Insert(0, 10);
            Console.WriteLine("After insert 10 in index of 0:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            // Test2.2:在索引为2(即第3个节点)的位置插入单个节点
            linkedList.Insert(2, 20);
            Console.WriteLine("After insert 20 in index of 2:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            // Test2.3:在索引为5(即最后一个节点)的位置插入单个节点
            linkedList.Insert(5, 30);
            Console.WriteLine("After insert 30 in index of 5:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            Console.WriteLine("----------------------------");

            // Test3.1:移除索引为5(即最后一个节点)的节点
            linkedList.RemoveAt(5);
            Console.WriteLine("After remove an node in index of 5:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            // Test3.2:移除索引为0(即第一个节点)的节点
            linkedList.RemoveAt(0);
            Console.WriteLine("After remove an node in index of 0:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            // Test3.3:移除索引为2(即第三个节点)的节点
            linkedList.RemoveAt(2);
            Console.WriteLine("After remove an node in index of 2:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.WriteLine(linkedList[i]);
            }
            Console.WriteLine("----------------------------");
        } 
        #endregion
    }

  测试结果如下图所示:

  ①顺序插入4个新节点

  ②在指定位置插入新节点

  ③在指定位置移除某个节点

三、双链表基础

3.1 双链表的节点结构

  与单链表不同的是,双链表有两个指针域,一个指向前驱节点,另一个指向后继节点。

3.2 双链表的总体结构

  双链表中,每个节点都有两个指针,指向前驱和后继,这样可以方便地找到某个节点的前驱节点和后继节点,这在某些场合中是非常实用的。

四、双链表实现

4.1 双链表节点的定义

    public class DbNode<T>
    {
        public T Item { get; set; }
        public DbNode<T> Prev { get; set; }
        public DbNode<T> Next { get; set; }

        public DbNode()
        {
        }

        public DbNode(T item)
        {
            this.Item = item;
        }
    }

  与单链表的节点定义不同的是,多了一个指向前驱节点的Prev指针域,可以方便地找到某个节点的前驱节点,从而不必重新遍历一次。

4.2 双链表中插入新节点

  ①默认在尾节点之后插入新节点

        public void AddAfter(T value)
        {
            DbNode<T> newNode = new DbNode<T>(value);
            if (this.head == null)
            {
                // 如果链表当前为空则置为头结点
                this.head = newNode;
            }
            else
            {
                DbNode<T> lastNode = this.GetNodeByIndex(this.count - 1);
                // 调整插入节点与前驱节点指针关系
                lastNode.Next = newNode;
                newNode.Prev = lastNode;
            }
            this.count++;
        }

  ②可选在尾节点之前插入新节点

        public void AddBefore(T value)
        {
            DbNode<T> newNode = new DbNode<T>(value);
            if (this.head == null)
            {
                // 如果链表当前为空则置为头结点
                this.head = newNode;
            }
            else
            {
                DbNode<T> lastNode = this.GetNodeByIndex(this.count - 1);
                DbNode<T> prevNode = lastNode.Prev;
                // 调整倒数第2个节点与插入节点的关系
                prevNode.Next = newNode;
                newNode.Prev = prevNode;
                // 调整倒数第1个节点与插入节点的关系
                lastNode.Prev = newNode;
                newNode.Next = lastNode;
            }
            this.count++;
        }

  典型的四个步骤,调整插入节点与尾节点前驱节点的关系、插入节点与尾节点的关系。

  当然,还可以在指定的位置之前或之后插入新节点,例如InsertAfter和InsertBefore方法,代码详见下面4.3后面的完整实现。

4.3 双链表中移除某个节点

        public void RemoveAt(int index)
        {
            if (index == 0)
            {
                this.head = this.head.Next;
            }
            else
            {
                DbNode<T> prevNode = this.GetNodeByIndex(index - 1);
                if (prevNode.Next == null)
                {
                    throw new ArgumentOutOfRangeException("index", "索引超出范围");
                }

                DbNode<T> deleteNode = prevNode.Next;
                DbNode<T> nextNode = deleteNode.Next;
                prevNode.Next = nextNode;
                if(nextNode != null)
                {
                    nextNode.Prev = prevNode;
                }

                deleteNode = null;
            }
            this.count--;
        }

  这里只需要将前驱节点的Next指针指向待删除节点的后继节点,将后继节点的Prev指针指向待删除节点的前驱节点即可。

  至此,关键部分的代码已介绍完毕,下面给出完整的双链表模拟实现代码:

    /// <summary>
    /// 双链表的模拟实现
    /// </summary>
    public class MyDoubleLinkedList<T>
    {
        private int count; // 字段:当前链表节点个数
        private DbNode<T> head; // 字段:当前链表的头结点

        // 属性:当前链表节点个数
        public int Count
        {
            get
            {
                return this.count;
            }
        }

        // 索引器
        public T this[int index]
        {
            get
            {
                return this.GetNodeByIndex(index).Item;
            }
            set
            {
                this.GetNodeByIndex(index).Item = value;
            }
        }

        public MyDoubleLinkedList()
        {
            this.count = 0;
            this.head = null;
        }

        // Method01:根据索引获取节点
        private DbNode<T> GetNodeByIndex(int index)
        {
            if (index < 0 || index >= this.count)
            {
                throw new ArgumentOutOfRangeException("index", "索引超出范围");
            }

            DbNode<T> tempNode = this.head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.Next;
            }

            return tempNode;
        }

        // Method02:在尾节点后插入新节点
        public void AddAfter(T value)
        {
            DbNode<T> newNode = new DbNode<T>(value);
            if (this.head == null)
            {
                // 如果链表当前为空则置为头结点
                this.head = newNode;
            }
            else
            {
                DbNode<T> lastNode = this.GetNodeByIndex(this.count - 1);
                // 调整插入节点与前驱节点指针关系
                lastNode.Next = newNode;
                newNode.Prev = lastNode;
            }
            this.count++;
        }

        // Method03:在尾节点前插入新节点
        public void AddBefore(T value)
        {
            DbNode<T> newNode = new DbNode<T>(value);
            if (this.head == null)
            {
                // 如果链表当前为空则置为头结点
                this.head = newNode;
            }
            else
            {
                DbNode<T> lastNode = this.GetNodeByIndex(this.count - 1);
                DbNode<T> prevNode = lastNode.Prev;
                // 调整倒数第2个节点与插入节点的关系
                prevNode.Next = newNode;
                newNode.Prev = prevNode;
                // 调整倒数第1个节点与插入节点的关系
                lastNode.Prev = newNode;
                newNode.Next = lastNode;
            }
            this.count++;
        }

        // Method04:在指定位置后插入新节点
        public void InsertAfter(int index, T value)
        {
            DbNode<T> tempNode;
            if (index == 0)
            {
                if (this.head == null)
                {
                    tempNode = new DbNode<T>(value);
                    this.head = tempNode;
                }
                else
                {
                    tempNode = new DbNode<T>(value);
                    tempNode.Next = this.head;
                    this.head.Prev = tempNode;
                    this.head = tempNode;
                }
            }
            else
            {
                DbNode<T> prevNode = this.GetNodeByIndex(index); // 获得插入位置的节点
                DbNode<T> nextNode = prevNode.Next; // 获取插入位置的后继节点
                tempNode = new DbNode<T>(value);
                // 调整插入节点与前驱节点指针关系
                prevNode.Next = tempNode;
                tempNode.Prev = prevNode;
                // 调整插入节点与后继节点指针关系
                if (nextNode != null)
                {
                    tempNode.Next = nextNode;
                    nextNode.Prev = tempNode;
                }
            }
            this.count++;
        }

        // Method05:在指定位置前插入新节点
        public void InsertBefore(int index, T value)
        {
            DbNode<T> tempNode;
            if (index == 0)
            {
                if (this.head == null)
                {
                    tempNode = new DbNode<T>(value);
                    this.head = tempNode;
                }
                else
                {
                    tempNode = new DbNode<T>(value);
                    tempNode.Next = this.head;
                    this.head.Prev = tempNode;
                    this.head = tempNode;
                }
            }
            else
            {
                DbNode<T> nextNode = this.GetNodeByIndex(index); // 获得插入位置的节点
                DbNode<T> prevNode = nextNode.Prev; // 获取插入位置的前驱节点
                tempNode = new DbNode<T>(value);
                // 调整插入节点与前驱节点指针关系
                prevNode.Next = tempNode;
                tempNode.Prev = prevNode;
                // 调整插入节点与后继节点指针关系
                tempNode.Next = nextNode;
                nextNode.Prev = tempNode;
            }
            this.count++;
        }

        // Method06:移除指定位置的节点
        public void RemoveAt(int index)
        {
            if (index == 0)
            {
                this.head = this.head.Next;
            }
            else
            {
                DbNode<T> prevNode = this.GetNodeByIndex(index - 1);
                if (prevNode.Next == null)
                {
                    throw new ArgumentOutOfRangeException("index", "索引超出范围");
                }

                DbNode<T> deleteNode = prevNode.Next;
                DbNode<T> nextNode = deleteNode.Next;
                prevNode.Next = nextNode;
                if(nextNode != null)
                {
                    nextNode.Prev = prevNode;
                }

                deleteNode = null;
            }
            this.count--;
        }
    }

4.4 双链表模拟实现的简单测试

  这里跟单链表一样,进行几个简单的测试:一是顺序插入(默认在尾节点之后)4个新节点,二是在尾节点之前和在指定索引位置插入新节点,三是移除指定索引位置的节点,四是修改某个节点的Item值。测试代码如下所示。

        static void MyDoubleLinkedListTest()
        {
            MyDoubleLinkedList<int> linkedList = new MyDoubleLinkedList<int>();
            // Test1:顺序插入4个节点
            linkedList.AddAfter(0);
            linkedList.AddAfter(1);
            linkedList.AddAfter(2);
            linkedList.AddAfter(3);

            Console.WriteLine("The nodes in the DoubleLinkedList:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("----------------------------");
            // Test2.1:在尾节点之前插入2个节点
            linkedList.AddBefore(10);
            linkedList.AddBefore(20);
            Console.WriteLine("After add 10 and 20:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            // Test2.2:在索引为2(即第3个节点)的位置之后插入单个节点
            linkedList.InsertAfter(2, 50);
            Console.WriteLine("After add 50:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            // Test2.3:在索引为2(即第3个节点)的位置之前插入单个节点
            linkedList.InsertBefore(2, 40);
            Console.WriteLine("After add 40:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("----------------------------");
            // Test3.1:移除索引为7(即最后一个节点)的位置的节点
            linkedList.RemoveAt(7);
            Console.WriteLine("After remove an node in index of 7:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            // Test3.2:移除索引为0(即第一个节点)的位置的节点的值
            linkedList.RemoveAt(0);
            Console.WriteLine("After remove an node in index of 0:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            // Test3.3:移除索引为2(即第3个节点)的位置的节点
            linkedList.RemoveAt(2);
            Console.WriteLine("After remove an node in index of 2:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("----------------------------");
            // Test4:修改索引为2(即第3个节点)的位置的节点的值
            linkedList[2] = 9;
            Console.WriteLine("After update the value of node in index of 2:");
            for (int i = 0; i < linkedList.Count; i++)
            {
                Console.Write(linkedList[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("----------------------------");
        }

  测试结果如下图所示。

五、.NET中的ListDictionary与LinkedList<T>

  在.NET中,已经为我们提供了单链表和双链表的实现,它们分别是ListDictionary与LinkedList<T>。从名称可以看出,单链表的实现ListDictionary不是泛型实现,而LinkedList是泛型实现,它们又到底有什么区别呢,借助Reflector去看看吧。

5.1 ListDictionary—基于key/value的单链表

  ListDictionary位于System.Collection.Specialized下,它是基于键值对(Key/Value)的集合,微软给出的建议是:通常用于包含10个或10个以下项的集合。

  它的节点的数据域是一个键值对,而不是一个简单的value。

5.2 LinkedList—神奇的泛型双向链表

  在.NET中,LinkedList<T>是使用地比较多的链表实现类,它位于System.Collections.Generic下,是一个通用的双向链表类,它不支持随机访问(即索引访问),但它实现了很多的新增节点的方法,例如:AddAfter、AddBefore、AddFirst以及AddLast等。其中,AddFirst是在现有节点之后添加新节点,AddBefore则是在现有节点之前添加新节点,AddFirst是在开头处添加,而AddLast则是在末尾处添加。

参考资料

(1)程杰,《大话数据结构》

(2)陈广,《数据结构(C#语言描述)》

(3)段恩泽,《数据结构(C#语言版)》

(4)率辉,《数据结构高分笔记(2015版)》

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

HashMap实现原理分析(Java源码剖析)内部实现存储结构-字段功能实现-方法Map中各实现类的总结小结

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对Ha...

812
来自专栏每日一篇技术文章

Swift3.0 - 字典

522
来自专栏拭心的安卓进阶之路

Java 集合深入理解(13):Stack 栈

今天心情不错,再来一篇 Stack ! 数据结构中的 栈 数据结构中,栈是一种线性数据结构,遵从 LIFO(后进先出)的操作顺序,所有操作都是在顶部进行 ...

20910
来自专栏ml

hihocoder-平衡树·SBT

 http://hihocoder.com/problemset/problem/1337 #1337 : 平衡树·SBT 时间限制:10000ms 单点时限:...

2685
来自专栏calmound

Is It A Tree?(并查集)

判断树是否唯一 1.只有一个根节点,(1)在一棵树上一个根节点。1 2 3 2就是两个根节点(1)只有一棵树 2.不成环,入度不大于1 由于数组运行超界导致wa...

3366
来自专栏码匠的流水账

聊聊flink的OperatorStateBackend

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/OperatorSta...

2112
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

1904
来自专栏王硕

原 pg查询树的简单解读

36513
来自专栏JMCui

ArrayList 和 LinkedList的执行效率比较

一、概念:     一般我们都知道ArrayList* 由一个数组后推得到的 List。作为一个常规用途的对象容器使用,用于替换原先的 Vector。允许我们快...

3659
来自专栏null的专栏

剑指Offer——编程题的Java实现

声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

7643

扫码关注云+社区