Creando una lista vinculada muy simple

Estoy tratando de crear una lista vinculada solo para ver si puedo, y estoy teniendo problemas para entenderlo. ¿Alguien tiene un ejemplo de una implementación muy simple de la lista vinculada usando C #? Todos los ejemplos que he encontrado hasta ahora son bastante exagerados.

Una lista vinculada, en su núcleo es un grupo de nodos unidos entre sí.

Por lo tanto, debe comenzar con una clase de nodo simple:

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

Entonces, su lista vinculada tendrá como miembro un nodo que representa la cabeza (inicio) de la lista:

 public class LinkedList { private Node head; } 

Luego necesita agregar funcionalidad a la lista agregando métodos. Por lo general, implican algún tipo de recorrido a lo largo de todos los nodos.

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

Además, insertar nuevos datos es otra operación común:

 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; } 

Esto debería proporcionar un buen punto de partida.

Basado en lo que dijo @jjnguy, y arreglando el error en sus PrintAllNodes (), aquí está el ejemplo completo de la aplicación de consola:

 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(); } } 

Este es lindo:

  namespace ConsoleApplication1 { // T is the type of data stored in a particular instance of GenericList. public class GenericList { 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; } } } 

Código de prueba:

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

Lo encontré en msdn aquí

Soy un principiante y esto me ayudó:

 class List { private Element Root; } 

Primero creas la lista de clases que contendrá todos los métodos. Luego creas el Node-Class, lo llamaré Element

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

Luego puede comenzar a agregar métodos a su clase List. Aquí hay un método de ‘agregar’, por ejemplo.

 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; } } 

utilizando:

 LinkedList sample = new LinkedList(); sample.add(new Node("first")); sample.Add(new Node("second")) 

Aquí hay uno con IEnumerable y un método Recursive Reverse aunque no es más rápido que el while while en el método Reverse ambos son O (n):

  public class LinkedList : IEnumerable { private Node _head = null; public Node Add(T value) { var node = new Node {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 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 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 current, Node prev) { if (current.Next == null) { _head = current; _head.Next = prev; return; } var next = current.Next; current.Next = prev; reverseRecurive(next, current); } public IEnumerator Enumerator() { var current = _head; while (current != null) { yield return current.Value; current = current.Next; } } public IEnumerator GetEnumerator() { return Enumerator(); } } public class Node { public T Value { get; set; } public Node Next { get; set; } } 

Una simple búsqueda en Google arrojó este artículo:

http://www.functionx.com/csharp1/examples/linkedlist.htm

se ve muy simple a primera vista …

Además, cuando esté listo para el siguiente nivel, use el reflector para examinar la propia LinkedList de Microsoft

Aquí hay una buena implementación.

  1. Es corto, pero implementado Add (x), Delete (x), Contain (x) e Print ().
  2. Evita un proceso especial cuando se agrega a la lista vacía o elimina el primer elemento. Mientras que la mayoría de los otros ejemplos hicieron un proceso especial cuando se borró el primer elemento.
  3. La lista puede contener cualquier tipo de datos.

     using System; class Node : LinkedList { // Why inherit from LinkedList? A: We need to use polymorphism. public Type value; public Node(Type value) { this.value = value; } } class LinkedList { Node next; // This member is treated as head in class LinkedList, but treated as next element in class Node. ///  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.  protected LinkedList Previos(Type x) { LinkedList 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. } ///  return value: true = success ; false = x not exist  public bool Contain(Type x) { return Previos(x).next != null ? true : false; } ///  return value: true = success ; false = fail to add. Because x already exist. ///  // 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 p = Previos(x); if (p.next != null) // Find x already in list return false; p.next = new Node(x); return true; } ///  return value: true = success ; false = x not exist  public bool Delete(Type x) { LinkedList p = Previos(x); if (p.next == null) return false; //Node node = p.next; p.next = p.next.next; //node.Dispose(); // GC dispose automatically. return true; } public void Print() { Console.Write("List: "); for (Node node = next; node != null; node = node.next) Console.Write(node.value.ToString() + " "); Console.WriteLine(); } } class Test { static void Main() { LinkedList LL = new LinkedList(); 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(); } } 

Por cierto, la implementación en http://www.functionx.com/csharp1/examples/linkedlist.htm tiene algún problema:

  1. Delete () fallará cuando solo haya 1 elemento. (Lanzar excepción en la línea “Head.Next = Current.Next;” porque Current es nulo.)
  2. Eliminar (posición) fallará al eliminar el primer elemento. En otras palabras, la llamada Eliminar (0) fallará.

Estoy dando un extracto del libro “C # 6.0 en una shell de nuez de Joseph Albahari y Ben Albahari”

Aquí hay una demostración sobre el uso de LinkedList:

 var tune = new LinkedList(); 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 miNode = tune.Find ("mi"); tune.Remove (miNode); // re - fa tune.AddFirst (miNode); // mi- re - fa foreach (string s in tune) Console.WriteLine (s); 
 public class Node { public T item; public Node next; public Node() { this.next = null; } } class LinkList { public Node head { get; set; } public LinkList() { this.head = null; } public void AddAtHead(T item) { Node newNode = new Node(); newNode.item = item; if (this.head == null) { this.head = newNode; } else { newNode.next = head; this.head = newNode; } } public void AddAtTail(T item) { Node newNode = new Node(); newNode.item = item; if (this.head == null) { this.head = newNode; } else { Node 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 temp = head; Node 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 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 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; } } 

Prueba con:

 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 hizo un buen trabajo, pero aquí hay una versión más concisa.

 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; } } } 

Agrega una clase de nodo.
A continuación, agregue una clase LinkedList para implementar la lista vinculada
Agregue una clase de prueba para ejecutar la lista vinculada

 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(); } } } 

progtwig c # simple para implementar Single Link List con operaciones AddItemStart, AddItemEnd, RemoveItemStart, RemoveItemEnd y 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(); } } } 

La respuesta seleccionada no tiene un iterador; es más básico, pero tal vez no tan útil.

Aquí hay uno con un iterador / enumerador. Mi implementación se basa en la bolsa de Sedgewick; ver http://algs4.cs.princeton.edu/13stacks/Bag.java.html

 void Main() { var b = new Bag(); 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 : IEnumerable { public Node first;// first node in list public class Node { public T item; public Node next; public Node(T item) { this.item = item; } } public void Add(T item) { Node oldFirst = first; first = new Node(item); first.next = oldFirst; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator GetEnumerator() { return new BagEnumerator(this); } public class BagEnumerator : IEnumerator { private Node _head; private Bag _bag; private Node _curNode; public BagEnumerator(Bag bag) { _bag = bag; _head = bag.first; _curNode = default(Node); } 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); ; } public void Dispose() { } } }