开发者社区> 杨俊明> 正文

数据结构C#版笔记--单链表(LinkList)

简介: 上一篇学习了"顺序表(SeqList)",这一篇来看下“单链表(LinkList)”。在上一篇的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动。
+关注继续查看

上一篇学习了"顺序表(SeqList)",这一篇来看下“单链表(LinkList)”。在上一篇的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动。如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大。

 

而链表结构正好相反,先来看下结构:

每个元素至少具有二个属性:data和next。data用来存放数据,而next用来指出它后面的元素是谁(有点“指针”的意思)。

链表中的元素,通常也称为节点Node,下面是泛型版本的Node.cs

namespace 线性表
{
    public class Node<T>
    {
        private T data;
        private Node<T> next;

        public Node(T val, Node<T> p) 
        {
            data = val;
            next = p;
        }

        public Node(Node<T> p) 
        {
            next = p;
        }

        public Node(T val) 
        {
            data = val;
            next = null;
        }


        public Node() 
        {
            data = default(T);
            next = null;
        }

        public T Data 
        {
            get { return data; }
            set { data = value; }
        }

        public Node<T> Next 
        {
            get { return next; }
            set { next = value; }
        }
    }
}

链表在存储上并不要求所有元素按顺序存储,因为用节点的next就能找到下一个节点,这好象一根“用珠子串成的链子”,要找到其中的某一颗珠子,只要从第一

颗节点(通常称为Head节点)开始,不断根据next指向找到下一个,直到找到需要的节点为止。


链表中需要有一个Head节点做为开始,这跟顺序表有所不同,下面是单链表的实现:

using System;
using System.Text;

namespace 线性表
{
    public class LinkList<T> : IListDS<T>
    {
        private Node<T> head;

        public Node<T> Head
        {
            get { return head; }
            set { head = value; }
        }

        public LinkList()
        {
            head = null;
        }

        /// <summary>
        /// 类索引器
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index] 
        {
            get 
            {
                return this.GetItemAt(index);
            }
        }

        /// <summary>
        /// 返回单链表的长度
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            Node<T> p = head;
            int len = 0;
            while (p != null)
            {
                len++;
                p = p.Next;
            }
            return len;
        }

        /// <summary>
        /// 清空
        /// </summary>
        public void Clear()
        {
            head = null;
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return head == null;
        }

        /// <summary>
        /// 在最后附加元素
        /// </summary>
        /// <param name="item"></param>
        public void Append(T item)
        {
            Node<T> d = new Node<T>(item);
            Node<T> n = new Node<T>();

            if (head == null)
            {
                head = d;
                return;
            }

            n = head;
            while (n.Next != null)
            {
                n = n.Next;
            }
            n.Next = d;
        }

        //前插
        public void InsertBefore(T item, int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }

            //在最开头插入
            if (i == 0)
            {
                Node<T> q = new Node<T>(item);
                q.Next = Head;//把"头"改成第二个元素
                head = q;//把自己设置为"头"
                return;
            }

            Node<T> n = head;
            Node<T> d = new Node<T>();
            int j = 0;

            //找到位置i的前一个元素d
            while (n.Next != null && j < i)
            {
                d = n;
                n = n.Next;
                j++;
            }

            if (n.Next == null) //说明是在最后节点插入(即追加)
            {
                Node<T> q = new Node<T>(item);
                n.Next = q;
                q.Next = null;
            }
            else
            {
                if (j == i)
                {
                    Node<T> q = new Node<T>(item);
                    d.Next = q;
                    q.Next = n;
                }
            }
        }

        /// <summary>
        /// 在位置i后插入元素item
        /// </summary>
        /// <param name="item"></param>
        /// <param name="i"></param>
        public void InsertAfter(T item, int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }

            if (i == 0)
            {
                Node<T> q = new Node<T>(item);
                q.Next = head.Next;
                head.Next = q;
                return;
            }

            Node<T> p = head;
            int j = 0;

            while (p != null && j < i)
            {
                p = p.Next;
                j++;
            }
            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p.Next;
                p.Next = q;
            }
            else             
            {
                Console.WriteLine("Position is error!");
            }
        }

        /// <summary>
        /// 删除位置i的元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T RemoveAt(int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("Link is empty or Position is error!");
                return default(T);
            }

            Node<T> q = new Node<T>();
            if (i == 0)
            {
                q = head;
                head = head.Next;
                return q.Data;
            }

            Node<T> p = head;
            int j = 0;

            while (p.Next != null && j < i)
            {
                j++;
                q = p;
                p = p.Next;
            }

            if (j == i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                Console.WriteLine("The node is not exist!");
                return default(T);
            }
        }

        /// <summary>
        /// 获取指定位置的元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T GetItemAt(int i)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty!");
                return default(T);
            }

            Node<T> p = new Node<T>();
            p = head;

            if (i == 0) 
            { 
                return p.Data; 
            }

            int j = 0;

            while (p.Next != null && j < i)
            {
                j++;
                p = p.Next;
            }

            if (j == i)
            {
                return p.Data;
            }
            else
            {
                Console.WriteLine("The node is not exist!");
                return default(T);
            }
        }

        //按元素值查找索引
        public int IndexOf(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            Node<T> p = new Node<T>();
            p = head;
            int i = 0;
            while (!p.Data.Equals(value) && p.Next != null)
            {
                p = p.Next;
                i++;
            }
            return i;
        }

        /// <summary>
        /// 元素反转
        /// </summary>
        public void Reverse()
        {
            LinkList<T> result = new LinkList<T>();            
            Node<T> t = this.head;
            result.Head = new Node<T>(t.Data);
            t = t.Next;

            //(把当前链接的元素从head开始遍历,逐个插入到另一个空链表中,这样得到的新链表正好元素顺序跟原链表是相反的)
            while (t!=null)
            {                
                result.InsertBefore(t.Data, 0);
                t = t.Next;
            }
            this.head = result.head;//将原链表直接挂到"反转后的链表"上
            result = null;//显式清空原链表的引用,以便让GC能直接回收
        }


        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            Node<T> n = this.head;
            sb.Append(n.Data.ToString() + ",");
            while (n.Next != null)
            {
                sb.Append(n.Next.Data.ToString() + ",");
                n = n.Next;
            }
            return sb.ToString().TrimEnd(',');

        }
    }
}

 下面是单链表插入和删除的算法图解:

可以看到:链表在元素插入/删除时,无需对后面的元素进行移动,只需要修改自身以及相邻节点的next指向即可,所以插入/删除元素的开销要比顺序表小得多。但是也应该注意到,其它操作比如:查找元素,反转倒置链表等,有可能需要遍历整个链表中的所有元素。

测试代码片断:

            Console.WriteLine("-------------------------------------");
            Console.WriteLine("单链表测试开始...");
            LinkList<string> link = new LinkList<string>();
            link.Head = new Node<string>("x");
            link.InsertBefore("w", 0);
            link.InsertBefore("v", 0);
            link.Append("y");
            link.InsertBefore("z", link.Count());
            Console.WriteLine(link.Count());//5
            Console.WriteLine(link.ToString());//v,w,x,y,z
            Console.WriteLine(link[1]);//w
            Console.WriteLine(link[0]);//v
            Console.WriteLine(link[4]);//z
            Console.WriteLine(link.IndexOf("z"));//4
            Console.WriteLine(link.RemoveAt(2));//x
            Console.WriteLine(link.ToString());//v,w,y,z
            link.InsertBefore("x", 2);
            Console.WriteLine(link.ToString());//v,w,x,y,z
            Console.WriteLine(link.GetItemAt(2));//x
            link.Reverse();
            Console.WriteLine(link.ToString());//z,y,x,w,v
            link.InsertAfter("1", 0);
            link.InsertAfter("2", 1);
            link.InsertAfter("6", 5);
            link.InsertAfter("8", 7);
            link.InsertAfter("A", 10);//Position is error!

            Console.WriteLine(link.ToString()); //z,1,2,y,x,w,6,v,8

至于具体在实际应用中应该选用顺序表 or 链表,主要是看:对于元素插入/删除的频繁程度以及对于内存分配的苛刻程度。 如果不要求一开始就分配一组连续的内存区域,可以根据元素的增加而自动加大内存的使用量,或者插入/删除的次数很多,那么建议使用链表,反之用顺序表。

 

最后指出:可以给节点再添加一个prev元素,用于指出前一个节点是谁,即同时有next和prev二个指向,这种改进后的链表称为“双向链表”,它有助于某些情况下减少遍历循环的次数,本文中的这种仅有一个next指向的链表,称为“单链表”。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构和算法之链表 | 链表介绍(难度级别:简单)
数据结构和算法之链表 | 链表介绍(难度级别:简单)
51 0
Java Collection笔记之ArrayList
<div class="markdown_views"> <h1 id="1前言">1、前言</h1> <p>ArrayList 是一个数组队列,相当于动态数组。与Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。</p> <p><
1460 0
HBase数据结构(读书笔记 )
背景:      最近在做一些跟大数据相关的东西,涉及到数据的存储和分析,考虑各个方面,选择使用HBase进行存储,使用原生Java API进行数据分析,之后会陆续写一系列来说明最近做的东西,给像我这样未曾涉及过这个领域的人一点儿idea。
1204 0
从 0 到 1 通过 Flink + Tablestore 进行大数据处理与分析
阿里云实时计算Flink版是一套基于 Apache Flink 构建的⼀站式实时大数据分析平台。在大数据场景下,实时计算 Flink 可提供端到端亚秒级实时数据流批处理能力。表格存储 Tablestore (又名 OTS)是阿里云自研的多模型结构化数据存储,可提供海量结构化数据的存储、查询分析服务。表格存储的双引擎架构支持千万TPS和毫秒级延迟的服务能力,可作为大数据计算的极佳上下游存储。
491 0
单链表的各种实现,绝对全(学习数据结构必看!)
单链表的各种实现,绝对全(学习数据结构必看!)
31 0
WCF 笔记 (2) - 传输泛型 List 对象
在做邮件服务的时候遇到一个问题: 服务器端有个方法参数是个List 类型。当在客户端传参数的时候 ,你即使传个List类型的参数,也还是提示参数类型错误。 相关解决方法:http://www.cnblogs.com/wizardwu/archive/2009/08/09/1542102.html
667 0
history命令解析_学习笔记
时间:2017.11.13 作者:李强 参考:man,info,magedu讲义 声明:以下英文纯属个人翻译,英文B级,欢迎纠正,盗版不纠,才能有限,希望不误人子弟为好。 1、使用目的与场景     实现快速操作命令的一种方式 2、官方说明     Display or manipulate the history list. 3、写在前面     首先这里有两个概念history list和history file。
799 0
AndroidStudio笔记(3)提升效率的 Live Templates
前言 安卓开发者现如今主流的编译器就是 Android Studio (以下简称AS),而 AS 是基于 IDEA 而定制化开发的编译器。AS 为我们提供了大量能够减少编码量和编码效率的功能,本文着重讲解 AS 自带的 Live Templates 和自定义 Live Templates。
1197 0
+关注
杨俊明
菩提树下的杨过 http://yjmyzz.cnblogs.com/
1102
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载