数据结构与算法---C#实现LinkedList实例

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

这里创建一个单向链表，通过三个类来实现单向链表的基本操作：创建，新增(指定节点前，指定节点后)，删除，判断是否为空....

下面分别实现这三个类以及测试代码

LinkedListNode:链表的节点类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CADataStructureTest.LinkedList
{
    public class LinkedListNode
    {
        public object Data { get; private set; }

        public LinkedListNode Next { get; set; }

        public LinkedListNode(object dataValue)
            : this(dataValue, null)
        {
        }

        public LinkedListNode(object dataValue, LinkedListNode nextNode)
        {
            Data = dataValue;
            Next = nextNode;
        }
    }
}

LinkedList：链表类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CADataStructureTest.LinkedList
{
    public class LinkedList
    {
        private LinkedListNode firstNode;
        private LinkedListNode lastNode;
        private string name;

        public LinkedList(string listName)
        {
            name = listName;
            firstNode = lastNode = null;
        }
        public LinkedList()
            : this("list")
        {
        }

        public void InsertAtFront(object insertItem)
        {
            if (IsEmpty())
                firstNode = lastNode = new LinkedListNode(insertItem);
            else
                lastNode = lastNode.Next = new LinkedListNode(insertItem);
        }

        public void InsertAtBack(object insertItem)
        {
            if (IsEmpty())
                firstNode = lastNode = new LinkedListNode(insertItem);
            else
                firstNode = new LinkedListNode(insertItem, firstNode);
        }

        public object RemoveFromFront()
        {
            if (IsEmpty())
                throw new EmptyListException(name);
            object removeItem = firstNode.Data;

            if (firstNode == lastNode)
                firstNode = lastNode = null;
            else
                firstNode = firstNode.Next;
            return removeItem;
        }

        public object RemoveFromBack()
        {
            if (IsEmpty())
                throw new EmptyListException(name);

            object removeItem = lastNode.Data;
            if (firstNode == lastNode)
                firstNode = lastNode = null;
            else
            {
                LinkedListNode current = firstNode;

                while (current.Next != lastNode)
                    current = current.Next;
                lastNode = current;
                current.Next = null;
            }

            return removeItem;
        }

        public bool IsEmpty()
        {
            return firstNode == null;
        }

        public void Display()
        {
            if (IsEmpty())
            {
                Console.WriteLine("Empty " + name);
            }
            else
            {
                Console.Write("The " + name + " is: ");
                LinkedListNode current = firstNode;
                while (current != null)
                {
                    Console.Write(current.Data + " ");
                    current = current.Next;
                }
                Console.WriteLine("\n");
            }
        }

    }
}

EmptyListException：链表操作异常处理类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CADataStructureTest.LinkedList
{

    public class EmptyListException : Exception
    {
        public EmptyListException()
            : base("The list is empty")
        {
        }

        public EmptyListException(string name)
            : base("the " + name + " is empty")
        {
        }

        public EmptyListException(string exception, Exception inner)
            : base(exception, inner)
        {
        }
    }
}

测试代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using CADataStructureTest.LinkedList;
namespace CADataStructureTest
{
    class Program
    {
        static void Main(string[] args)
        {
            CADataStructureTest.LinkedList.LinkedList list = new CADataStructureTest.LinkedList.LinkedList();
            bool aBoolean = true;
            char aCharacter = '#';
            int anInteger = 9258;
            string aString = "DataStructure";

            list.InsertAtFront(aBoolean);
            list.Display();
            list.InsertAtFront(aCharacter);
            list.Display();
            list.InsertAtBack(anInteger);
            list.Display();
            list.InsertAtBack(aString);
            list.Display();

            object removedObject;

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

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

                removedObject = list.RemoveFromBack();
                Console.WriteLine(removedObject + " removed");
                list.Display();

                removedObject = list.RemoveFromBack();
                Console.WriteLine(removedObject + " removed");
                list.Display();
            }
            catch (CADataStructureTest.LinkedList.EmptyListException emptyListException)
            {
                Console.Error.WriteLine("\n" + emptyListException);
            }

            Console.ReadLine();
        }
        }
    }

效果如下: