【万丈高楼平地起 第一季 链表是怎样链成的】

 

一、链表
1.“连成一行”的、线性的数据项集合——用户可以在链表中的任何位置插入或删除数据。链表是自引用对象的线性集合（即序列）。其中的自引用类对象称为节点，节点之间通过引用（C/C++中叫做指针，高级语言称作引用）来链接，这便是“链表”一词的由来！程序通过首节点引用来访问链表，通过保存在前一个节点中的链接引用成员访问后继节点。习惯上将最后一个节点（即尾节点）的链接引用设为“null”表示链表结束。数据动态保存在链表中，程序员可以根据需要创建节点。节点中可以包含任意类型的数据，甚至是其他类型的对象。
2. 堆栈和队列也是线性数据结构，而且是一种受约束的链表。树却是非线性数据结构。

数组和链表比较：

1.        数组在构造时已确定大小，不能动态的根据需要分配内存。

2.        在链表中插入数据，只需修改两个引用，而数组需要移动N个元素。

3.        查找元素的时候，数组直接通过下标查找，效率会比链表快一些。链表访问元素只能从链表头开始遍历。

下面用C#语言实现单链表的基本操作。

开始写代码。新建一个控制台项目。

然后，新建类文件LinkedListLibrary.cs，写一个LinkList类，用来存放链表的属性和方法。

解释见注释。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace LinkedList
{
    /// <summary>
    /// ListNode类定义
    /// </summary>
    class ListNode
    {
        private object data;
        private ListNode next;
 
        public ListNode(object dataValue)
            : this(dataValue, null)
        {
        }
 
        public ListNode(object dataValue, ListNode nextNodes)
        {
            data = dataValue;
            next = nextNodes;
        }
 
        public object Data
        {
            get { return data; }
        }
 
        public ListNode Next
        {
            get
            {
                return next;
            }
            set
            {
                next = value;
            }
 
        }
    }
 
    /// <summary>
    /// List类定义
    /// </summary>
    public class List
    {
        private ListNode firstNode;
        private ListNode lastNoede;
        private string name;//显示字符串用
 
        public List(string listName)
        {
            name = listName;
            firstNode = lastNoede = null;
        }
 
        public List()
            : this("list")
        {
        }
 
        // 当这些方法用于多线程程序时，要用一个lock块来保证List类的多线程安全
        // 一个线程修改这些List对象内容时，其它线程不能同时修改这个对象
 
        /// <summary>
        /// 在列表前端插入元素，如果链表是空的，firstNode和lastNoede指向同一个节点。否则，firstNode指向新节点
        /// </summary>
        /// <param name="insertItem"></param>
        public void InsertAtFront(object insertItem)
        {
            lock (this)
            {
                if (IsEmpty())
                {
                    firstNode = lastNoede = new ListNode(insertItem);
                }
                else
                {
                    firstNode = new ListNode(insertItem, firstNode);
                }
            }
        }
 
        /// <summary>
        /// 在链表尾端插入元素，如果链表是空的，firstNode和lastNoede指向同一个节点。否则，lastNoede指向新节点
        /// </summary>
        /// <param name="insertItem"></param>
        public void InsertAtBack(object insertItem)
        {
            lock (this)
            {
                if (IsEmpty())
                {
                    firstNode = lastNoede = new ListNode(insertItem);
                }
                else
                {
                    lastNoede = lastNoede.Next = new ListNode(insertItem);
                }
            }
        }
 
        /// <summary>
        /// 删除链表的第一个节点
        /// </summary>
        public object RemoveFromFront()
        {
            lock (this)
            {
                if (IsEmpty())
                {
                    throw new EmptyListException(name);
                }
 
                object removeItem = firstNode.Data;
 
                // 重新分配引用
                if (firstNode == lastNoede)
                {
                    firstNode = lastNoede = null;
                }
                else
                {
                    firstNode = firstNode.Next;
                }
 
                return removeItem;
            }
        }
 
        /// <summary>
        /// 删除链表中的最后一个节点
        /// </summary>
        /// <returns></returns>
        public object RemoveFromBack()
        {
            lock (this)
            {
                if (IsEmpty())
                {
                    throw new EmptyListException(name);
                }
 
                object removeItem = lastNoede.Data;
 
                //重新分配引用
                if (firstNode == lastNoede)
                {
                    firstNode = lastNoede = null;
                }
                else
                {
                    ListNode current = firstNode;
 
                    //循环寻找lastNode
                    while (current.Next != lastNoede)
                    {
                        current = current.Next;
                    }
 
                    // current is a new lastNode
                    lastNoede = current;
                    current.Next = null;
                }
 
                return removeItem;
            }
        }
 
        /// <summary>
        /// 判断链表是否为空,即判断首节点是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            lock (this)
            {
                return firstNode == null;
            }
        }
 
        /// <summary>
        /// 输出链表内容
        /// </summary>
        virtual public void Print()
        {
            lock (this)
            {
                if (IsEmpty())
                {
                    Console.WriteLine("Empty " + name);
                    return;
                }
 
                Console.Write("The " + name + " is: ");
 
                ListNode current = firstNode;
 
                //循环遍历链表，输出Data
                while (current != null)
                {
                    Console.Write(current.Data + "  ");
                    current = current.Next;
                }
 
                Console.WriteLine("\n");
            }
        }
    }
 
    /// <summary>
    /// 链表异常类
    /// </summary>
    public class EmptyListException : ApplicationException
    {
        public EmptyListException(string name)
            : base("The " + name + " is empty.")
        {
 
        }
    }
}// end namespace LinkedList

LinkList类写好以后，我们就可以测试了。注意命名空间的引用。

测试文件：Program.cs

using System;
using LinkedListLibrary;
using StackInheritanceLibrary;
using QueueInheritanceLibrary;

namespace ListTest
{
class ListTest
    {
// 测试List
        static void Main(string[] args)
        {
// 新建一个List
            List list = new List();

// 新建一些不同类型的测试数据
            bool aBoolean = true;
char aChar = '$';
int anIntger = 34567;
string aString = "hello";

// use List insert methods
            list.InsertAtFront(aBoolean);
            list.Print();
            list.InsertAtFront(aChar);
            list.Print();
            list.InsertAtFront(anIntger);
            list.Print();
            list.InsertAtFront(aString);
            list.Print();

// use Lsit remove methods
            object removedObject;


try
            {
                removedObject = list.RemoveFromFront();
                Console.WriteLine(removedObject + " removed.");
                list.Print();

                removedObject = list.RemoveFromFront();
                Console.WriteLine(removedObject + " removed.");
                list.Print();

                removedObject = list.RemoveFromFront();
                Console.WriteLine(removedObject + " removed.");
                list.Print();

                removedObject = list.RemoveFromFront();
                Console.WriteLine(removedObject + " removed.");
                list.Print();

            }
catch (EmptyListException emptyListException)
            {
                Console.Error.WriteLine("\n" + emptyListException);
            }

            Console.ReadKey();
        }       
    }
}