创build一个非常简单的链接列表
我试图创build一个链表，只是为了看看我能不能，而且我很难find它。 有没有人有一个非常简单的实现使用C＃的链接列表的例子？ 到目前为止，我发现的所有例子都过分了。
一个链接列表，其核心是一堆链接在一起的节点。
所以，你需要从一个简单的Node类开始：
public class Node { public Node next; public Object data; } 然后你的链表将有一个节点作为一个节点代表头（开始）的列表：
public class LinkedList { private Node head; }
然后，您需要通过添加方法将function添加到列表中。 它们通常涉及到所有节点的某种遍历。
public void printAllNodes() { Node cur = head; while (cur.next != null) { Console.WriteLine(cur.data); cur = cur.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; }
这应该提供一个很好的起点……..
根据@jjnguy的说法，并在他的PrintAllNodes（）中修复这个bug，下面是完整的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(); } }
这一个很好：
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; } } }
testing代码：
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
我是一个初学者，这帮助了我：
class List { private Element Root; }
首先创build包含所有方法的类List。 然后你创buildNode-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); }
public class Node { private Object data; public Node next {get;set;} public Node(Object data) { this.data = data; } } public class Linkedlist { Node head; public void Add(Node n) { n.Next = this.Head; this.Head = n; } }
使用：
LinkedList sample = new LinkedList(); sample.add(new Node("first")); sample.Add(new Node("second"))
这里是一个IEnumerable和一个recursion反向的方法，虽然它不比在Reverse方法中的while循环都快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; } }
一个简单的谷歌search产生了这篇文章：
http://www.functionx.com/csharp1/examples/linkedlist.htm
第一眼看起来很简单
另外，当你准备好下一个级别时，使用reflection器来检查微软自己的LinkedList
这是一个很好的实现。
- 它很短，但实现了Add（x），Delete（x），Contain（x）和Print（）。
- 添加到空列表或删除第一个元素时避免特殊处理。 虽然其他大多数示例在删除第一个元素时做了特殊处理。
-
该列表可以包含任何数据types。
using System; class Node<Type> : LinkedList<Type> { // Why inherit from LinkedList? A: We need to use polymorphism. public Type value; public Node(Type value) { this.value = value; } } class LinkedList<Type> { Node<Type> next; // This member is treated as head in class LinkedList, but treated as next element in class Node. /// <summary> if x is in list, return previos pointer of x. (We can see any class variable as a pointer.) /// if not found, return the tail of the list. </summary> protected LinkedList<Type> Previos(Type x) { LinkedList<Type> p = this; // point to head for (; p.next != null; p = p.next) if (p.next.value.Equals(x)) return p; // find x, return the previos pointer. return p; // not found, p is the tail. } /// <summary> return value: true = success ; false = x not exist </summary> public bool Contain(Type x) { return Previos(x).next != null ? true : false; } /// <summary> return value: true = success ; false = fail to add. Because x already exist. /// </summary> // why return value? If caller want to know the result, they don't need to call Contain(x) before, the action waste time. public bool Add(Type x) { LinkedList<Type> p = Previos(x); if (p.next != null) // Find x already in list return false; p.next = new Node<Type>(x); return true; } /// <summary> return value: true = success ; false = x not exist </summary> public bool Delete(Type x) { LinkedList<Type> p = Previos(x); if (p.next == null) return false; //Node<Type> node = p.next; p.next = p.next.next; //node.Dispose(); // GC dispose automatically. return true; } public void Print() { Console.Write("List: "); for (Node<Type> node = next; node != null; node = node.next) Console.Write(node.value.ToString() + " "); Console.WriteLine(); } } class Test { static void Main() { LinkedList<int> LL = new LinkedList<int>(); if (!LL.Contain(0)) // Empty list Console.WriteLine("0 is not exist."); LL.Print(); LL.Add(0); // Add to empty list LL.Add(1); LL.Add(2); // attach to tail LL.Add(2); // duplicate add, 2 is tail. if (LL.Contain(0))// Find existed element which is head Console.WriteLine("0 is exist."); LL.Print(); LL.Delete(0); // Delete head LL.Delete(2); // Delete tail if (!LL.Delete(0)) // Delete non-exist element Console.WriteLine("0 is not exist."); LL.Print(); Console.ReadLine(); } }
顺便说一下，在http://www.functionx.com/csharp1/examples/linkedlist.htm中的实现有一些问题：;
- 只有1个元素时，Delete（）将失败。 （在“Head.Next = Current.Next;”行中抛出exception，因为Current为null。）
- 删除第一个元素时删除（位置）将失败，换句话说，调用Delete（0）将失败。
public class Node<T> { public T item; public Node<T> next; public Node() { this.next = null; } } class LinkList<T> { public Node<T> head { get; set; } public LinkList() { this.head = null; } public void AddAtHead(T item) { Node<T> newNode = new Node<T>(); newNode.item = item; if (this.head == null) { this.head = newNode; } else { newNode.next = head; this.head = newNode; } } public void AddAtTail(T item) { Node<T> newNode = new Node<T>(); newNode.item = item; if (this.head == null) { this.head = newNode; } else { Node<T> temp = this.head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; } } public void DeleteNode(T item) { if (this.head.item.Equals(item)) { head = head.next; } else { Node<T> temp = head; Node<T> tempPre = head; bool matched = false; while (!(matched = temp.item.Equals(item)) && temp.next != null) { tempPre = temp; temp = temp.next; } if (matched) { tempPre.next = temp.next; } else { Console.WriteLine("Value not found!"); } } } public bool searchNode(T item) { Node<T> temp = this.head; bool matched = false; while (!(matched = temp.item.Equals(item)) && temp.next != null) { temp = temp.next; } return matched; } public void DisplayList() { Console.WriteLine("Displaying List!"); Node<T> temp = this.head; while (temp != null) { Console.WriteLine(temp.item); temp = temp.next; } } }
public class DynamicLinkedList { private class Node { private object element; private Node next; public object Element { get { return this.element; } set { this.element = value; } } public Node Next { get { return this.next; } set { this.next = value; } } public Node(object element, Node prevNode) { this.element = element; prevNode.next = this; } public Node(object element) { this.element = element; next = null; } } private Node head; private Node tail; private int count; public DynamicLinkedList() { this.head = null; this.tail = null; this.count = 0; } public void AddAtLastPosition(object element) { if (head == null) { head = new Node(element); tail = head; } else { Node newNode = new Node(element, tail); tail = newNode; } count++; } public object GetLastElement() { object lastElement = null; Node currentNode = head; while (currentNode != null) { lastElement = currentNode.Element; currentNode = currentNode.Next; } return lastElement; } }
testing：
static void Main(string[] args) { DynamicLinkedList list = new DynamicLinkedList(); list.AddAtLastPosition(1); list.AddAtLastPosition(2); list.AddAtLastPosition(3); list.AddAtLastPosition(4); list.AddAtLastPosition(5); object lastElement = list.GetLastElement(); Console.WriteLine(lastElement); }
Dmytro做得很好，但是这是一个更简洁的版本。
class Program { static void Main(string[] args) { LinkedList linkedList = new LinkedList(1); linkedList.Add(2); linkedList.Add(3); linkedList.Add(4); linkedList.AddFirst(0); linkedList.Print(); } } public class Node { public Node(Node next, Object value) { this.next = next; this.value = value; } public Node next; public Object value; } public class LinkedList { public Node head; public LinkedList(Object initial) { head = new Node(null, initial); } public void AddFirst(Object value) { head = new Node(head, value); } public void Add(Object value) { Node current = head; while (current.next != null) { current = current.next; } current.next = new Node(null, value); } public void Print() { Node current = head; while (current != null) { Console.WriteLine(current.value); current = current.next; } } }
添加一个节点类。
然后添加一个LinkedList类来实现链表
添加一个testing类来执行链表
namespace LinkedListProject { public class Node { public Node next; public object data; } public class MyLinkedList { Node head; public Node AddNodes(Object data) { Node node = new Node(); if (node.next == null) { node.data = data; node.next = head; head = node; } else { while (node.next != null) node = node.next; node.data = data; node.next = null; } return node; } public void printnodes() { Node current = head; while (current.next != null) { Console.WriteLine(current.data); current = current.next; } Console.WriteLine(current.data); } } [TestClass] public class LinkedListExample { MyLinkedList linkedlist = new MyLinkedList(); [TestMethod] public void linkedlisttest() { linkedlist.AddNodes("hello"); linkedlist.AddNodes("world"); linkedlist.AddNodes("now"); linkedlist.printnodes(); } } }
简单的c＃程序来实现单链表的操作AddItemStart，AddItemEnd，RemoveItemStart，RemoveItemEnd和DisplayAllItems
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SingleLinkedList { class Program { Node head; Node current; int counter = 0; public Program() { head = new Node(); current = head; } public void AddStart(object data) { Node newnode = new Node(); newnode.next = head.next; newnode.data = data; head.next = newnode; counter++; } public void AddEnd(object data) { Node newnode = new Node(); newnode.data = data; current.next = newnode; current = newnode; counter++; } public void RemoveStart() { if (counter > 0) { head.next = head.next.next; counter--; } else { Console.WriteLine("No element exist in this linked list."); } } public void RemoveEnd() { if (counter > 0) { Node prevNode = new Node(); Node cur = head; while (cur.next != null) { prevNode = cur; cur = cur.next; } prevNode.next = null; } else { Console.WriteLine("No element exist in this linked list."); } } public void Display() { Console.Write("Head ->"); Node curr = head; while (curr.next != null) { curr = curr.next; Console.WriteLine(curr.data.ToString()); } } public class Node { public object data; public Node next; } static void Main(string[] args) { Program p = new Program(); p.AddEnd(2); p.AddStart(1); p.AddStart(0); p.AddEnd(3); p.Display(); p.RemoveStart(); Console.WriteLine("Removed node from Start"); p.Display(); Console.WriteLine("Removed node from End"); p.RemoveEnd(); p.Display(); Console.ReadKey(); } } }
所选答案没有迭代器; 这是更基本的，但也许没有那么有用。
这里是一个迭代器/枚举器。 我的实施基于Sedgewick的包; 请参阅http://algs4.cs.princeton.edu/13stacks/Bag.java.html
void Main() { var b = new Bag<string>(); b.Add("bike"); b.Add("erasmus"); b.Add("kumquat"); b.Add("beaver"); b.Add("racecar"); b.Add("barnacle"); foreach (var thing in b) { Console.WriteLine(thing); } } // Define other methods and classes here public class Bag<T> : IEnumerable<T> { public Node<T> first;// first node in list public class Node<T> { public T item; public Node<T> next; public Node(T item) { this.item = item; } } public void Add(T item) { Node<T> oldFirst = first; first = new Node<T>(item); first.next = oldFirst; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<T> GetEnumerator() { return new BagEnumerator<T>(this); } public class BagEnumerator<V> : IEnumerator<T> { private Node<T> _head; private Bag<T> _bag; private Node<T> _curNode; public BagEnumerator(Bag<T> bag) { _bag = bag; _head = bag.first; _curNode = default(Node<T>); } public T Current { get { return _curNode.item; } } object IEnumerator.Current { get { return Current; } } public bool MoveNext() { if (_curNode == null) { _curNode = _head; if (_curNode == null) return false; return true; } if (_curNode.next == null) return false; else { _curNode = _curNode.next; return true; } } public void Reset() { _curNode = default(Node<T>); ; } public void Dispose() { } } }
我正在从“Joseph Albahari和Ben Albahari的简介中的C＃6.0”一书中摘录一些内容，
以下是使用LinkedList的示例：
var tune = new LinkedList<string>(); tune.AddFirst ("do"); // do tune.AddLast ("so"); // do - so tune.AddAfter (tune.First, "re"); // do - re- so tune.AddAfter (tune.First.Next, "mi"); // do - re - mi- so tune.AddBefore (tune.Last, "fa"); // do - re - mi - fa- so tune.RemoveFirst(); // re - mi - fa - so tune.RemoveLast(); // re - mi - fa LinkedListNode<string> miNode = tune.Find ("mi"); tune.Remove (miNode); // re - fa tune.AddFirst (miNode); // mi- re - fa foreach (string s in tune) Console.WriteLine (s);
