如何在c#中将节点添加到单个链表中

Question

我已经开始学习C#中的算法。我一直在尝试自己创建一个链表算法（只是为了好玩）。然而，我有一个问题。我想知道，如何将节点添加到列表中？现在我有三个与节点交互的方法，但列表是空的，所以什么也没发生。

节点类

class Node {
    public int info;
    public Node link;
    public Node (int i)
    {
        info = i;
        link = null;
    }
}

SingleLinkedList类

class SingleLinkedList {
    private Node start;
    public SingleLinkedList ()
    {
        start = null;
    }
    public void CreateList() {
        //TODO: Create the linked list here
    }
    public void DisplayList() {
        Node p;
        if (start == null) {
            Console.WriteLine ("Your list is empty, idiot");
            return;
        }
        Console.WriteLine ("List is :  ");
        p = start;
        while (p != null) {
            Console.WriteLine (p.info + " ");
            p = p.link;
        }
        Console.WriteLine ();
    }
    public void CountNodes() {
        int n = 0;
        Node p = start;
        while (p != null) {
            n++;
            p = p.link;
        }
        Console.WriteLine ("Number of nodes in list is = " + n);
    }
    public bool Search (int x) {
        int position = 1;
        Node p = start;
        while (p != null) {
            if (p.info == x)
                break;
            position++;
            p = p.link;
        }
        if (p == null) {
            Console.WriteLine (x + "not found in list because use an idiot");
        } else {
            Console.WriteLine (x + "is at position " + position);
            return true;
        }
        return false;
    }
}

主

int choice, data;
SingleLinkedList list = new SingleLinkedList ();
Console.WriteLine ("1.Display List");
Console.WriteLine ("2.Count Nodes");
Console.WriteLine ("search for an integer");
Console.WriteLine ("Enter your choice master: ");
choice = Convert.ToInt32 (Console.ReadLine ());
switch (choice) {
case 1:
    list.DisplayList ();
    break;
case 2:
    list.CountNodes ();
    break;
case 3:
    Console.WriteLine ("Enter the element to be searched");
    data = Convert.ToInt32 (Console.ReadLine ());
    list.Search (data);
    break;
default:
    break;
}

如何在SingleLinkedList类中实现CreateList方法以将节点添加到列表中？

Answer 1

单链表模式维护一个指向第一个节点的指针/引用，每个项都包含一个指向列表中下一个节点的指示器/引用。附加到列表意味着找到空引用——无论是根引用还是链的末端——并用对新节点的引用填充：

public void Append(Node value)
{
    // check if we are adding to an empty list
    if (start == null)
        start = value;
    else
    {
        // find the last valid node
        Node curr;
        for (curr = start; curr.link != null; curr = curr.link);
        // add the item
        curr.link = value;
    }
}

这样做的缺点是，你的列表中的项目越多，找到末尾添加下一个项目所需的时间就越长。换句话说，这是一个O（N）运算，当你同时添加数千个项目时，真的很重要。对于100件左右的物品，你可能不会太注意到，但试着在列表中添加100000件。

幸运的是，只需跟踪列表中的最后一项（尾部），就可以将列表上的Append操作减少到O（1）。

public class SingleLinkedList
{
    Node head;
    Node tail;
    public void Append(Node value)
    {
        if (head == null)
            head = value;
        else
            tail.link = value;
        tail = value;
    }
}

现在，您可以以与不包含任何项目的列表相同的速度（几微秒或几微秒）将项目添加到百万项目列表中。当您从列表中删除项目时，只需记住更新tail即可。

---

至于搜索等，您可以实现IEnumerable并使用LINQ来完成所有工作。或者添加一个Items属性来为您做这件事：

public IEnumerable<int> Items
{
    get 
    {
        for (var next = head; next != null; next = next.link)
            yield return next.value;
    } 
}

现在，您可以使用以下内容测试列表中现有的项目：

if (list.Items.Any(i => i == somevalue))
{
}

Answer 2

public void AddNodeToList(Node nodeToBeAdded)
    {
        Node temp = null;
        if (start == null)
        {
            start = nodeToBeAdded;
        }
        else
        {
            temp = start;
            while (temp.link != null)
            {
                temp = temp.link;
            }
            temp.link = nodeToBeAdded;
        }
        nodeToBeAdded.link = null;
    }

 public void CreateList(Node[] nodesToBeAdded)
    {
        foreach (Node item in nodesToBeAdded)
        {
            this.AddNodeToList(item);
        }
    }