创建一个非常简单的链表

Question

我正在尝试创建一个链接列表,看看我是否可以,而且我无法理解它.有没有人有一个使用C#非常简单的链接列表实现的例子？到目前为止,我发现的所有例子都过分夸大了.

Answer 1

链接列表的核心是一堆链接在一起的节点.

因此,您需要从一个简单的Node类开始:

public class Node {
    public Node next;
    public Object data;
}

然后,您的链接列表将作为成员的一个节点表示列表的头部(开始):

public class LinkedList {
    private Node head;
}

然后,您需要通过添加方法向列表添加功能.它们通常涉及所有节点的某种遍历.

public void printAllNodes() {
    Node current = head;
    while (current != null) 
    {
        Console.WriteLine(current.data);
        current = current.next;
    }
}

此外,插入新数据是另一种常见操作:

public void Add(Object data) {
    Node toAdd = new Node();
    toAdd.data = data;
    Node current = head;
    // traverse all nodes (see the print all nodes method for an example)
    current.next = toAdd;
}

这应该是一个很好的起点.

Answer 2

基于@jjnguy所说的并修复了他的PrintAllNodes()中的错误,这里是完整的Console App示例:

public class Node
{
    public Node next;
    public Object data;
}

public class LinkedList
{
    private Node head;

    public void printAllNodes()
    {
        Node current = head;
        while (current != null)
        {
            Console.WriteLine(current.data);
            current = current.next;
        }
    }

    public void AddFirst(Object data)
    {
        Node toAdd = new Node();

        toAdd.data = data;
        toAdd.next = head;

        head = toAdd;
    }

    public void AddLast(Object data)
    {
        if (head == null)
        {
            head = new Node();

            head.data = data;
            head.next = null;
        }
        else
        {
            Node toAdd = new Node();
            toAdd.data = data;

            Node current = head;
            while (current.next != null)
            {
                current = current.next;
            }

            current.next = toAdd;
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Add First:");
        LinkedList myList1 = new LinkedList();

        myList1.AddFirst("Hello");
        myList1.AddFirst("Magical");
        myList1.AddFirst("World");
        myList1.printAllNodes();

        Console.WriteLine();

        Console.WriteLine("Add Last:");
        LinkedList myList2 = new LinkedList();

        myList2.AddLast("Hello");
        myList2.AddLast("Magical");
        myList2.AddLast("World");
        myList2.printAllNodes();

        Console.ReadLine();
    }
}

Answer 3

这个很好:

  namespace ConsoleApplication1
    {

    // T is the type of data stored in a particular instance of GenericList.
    public class GenericList<T>
    {
        private class Node
        {
            // Each node has a reference to the next node in the list.
            public Node Next;
            // Each node holds a value of type T.
            public T Data;
        }

        // The list is initially empty.
        private Node head = null;

        // Add a node at the beginning of the list with t as its data value.
        public void AddNode(T t)
        {
            Node newNode = new Node();
            newNode.Next = head;
            newNode.Data = t;
            head = newNode;
        }

        // The following method returns the data value stored in the last node in
        // the list. If the list is empty, the default value for type T is
        // returned.
        public T GetFirstAdded()
        {
            // The value of temp is returned as the value of the method. 
            // The following declaration initializes temp to the appropriate 
            // default value for type T. The default value is returned if the 
            // list is empty.
            T temp = default(T);

            Node current = head;
            while (current != null)
            {
                temp = current.Data;
                current = current.Next;
            }
            return temp;
        }
    }
}

测试代码:

static void Main(string[] args)
{
    // Test with a non-empty list of integers.
    GenericList<int> gll = new GenericList<int>();
    gll.AddNode(5);
    gll.AddNode(4);
    gll.AddNode(3);
    int intVal = gll.GetFirstAdded();
    // The following line displays 5.
    System.Console.WriteLine(intVal);
}

我遇到过MSDN上这里

Answer 4

这是一个带有IEnumerable和 Recursive Reverse 方法的方法，尽管它并不比方法中的 while 循环快，Reverse两者都是 O(n)：

   public class LinkedList<T> : IEnumerable
{
    private Node<T> _head = null;

    public Node<T> Add(T value)
    {
        var node = new Node<T> {Value = value};

        if (_head == null)
        {
            _head = node;
        }
        else
        {
            var current = _head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = node; //new head
        }

        return node;
    }

    public T Remove(Node<T> node)
    {
        if (_head == null)
            return node.Value;

        if (_head == node)
        {
            _head = _head.Next;
            node.Next = null;
            return node.Value;
        }

        var current = _head;
        while (current.Next != null)
        {
            if (current.Next == node)
            {
                current.Next = node.Next;
                return node.Value;
            }

            current = current.Next;
        }

        return node.Value;
    }

    public void Reverse()
    {
        Node<T> prev = null;
        var current = _head;

        if (current == null)
            return;

        while (current != null)
        {
            var next = current.Next;
            current.Next = prev;
            prev = current;
            current = next;
        }

        _head = prev;
    }

    public void ReverseRecurisve()
    {
        reverseRecurive(_head, null);
    }

    private void reverseRecurive(Node<T> current, Node<T> prev)
    {
        if (current.Next == null)
        {
            _head = current;
            _head.Next = prev;
            return;
        }

        var next = current.Next;
        current.Next = prev;
        reverseRecurive(next, current);
    }

    public IEnumerator<T> Enumerator()
    {
        var current = _head;
        while (current != null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }

    public IEnumerator GetEnumerator()
    {
        return Enumerator();
    }
}

public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }
}

Answer 5

我是初学者,这帮助了我:

class List
{
    private Element Root;
}

首先,创建将包含所有方法的类List.然后你创建Node-Class,我将其称为Element

class Element
{
    public int Value;
    public Element Next;
}

然后,您可以开始向List类添加方法.例如,这是一个"添加"方法.

public void Add(int value)
{
    Element newElement = new Element();
    newElement.Value = value;

    Element rootCopy = Root;
    Root = newElement;
    newElement.Next = rootCopy;

    Console.WriteLine(newElement.Value);
}