Criando uma linked list muito simples

Eu estou tentando criar uma lista ligada apenas para ver se posso, e estou tendo problemas em entender isso. Alguém tem um exemplo de uma implementação muito simples da linked list usando c #? Todos os exemplos que encontrei até agora são bastante exagerados.

Uma linked list, em sua essência, é um conjunto de nós interligados.

Então, você precisa começar com uma simples class Node:

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

Em seguida, sua linked list terá como membro um nó representando a cabeça (início) da lista:

 public class LinkedList { private Node head; } 

Então você precisa adicionar funcionalidades à lista adicionando methods. Eles geralmente envolvem algum tipo de travessia ao longo de todos os nós.

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

Além disso, a inserção de novos dados é outra operação comum:

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

Isso deve fornecer um bom ponto de partida.

Com base no que o @jjnguy disse, e corrigindo o bug no PrintAllNodes (), aqui está o exemplo completo do App Console:

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

Esse é legal:

  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 teste:

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

Eu encontrei no msdn aqui

Eu sou um iniciante e isso me ajudou:

 class List { private Element Root; } 

Primeiro você cria a lista de classs que conterá todos os methods. Então você cria o Node-Class, eu vou chamá-lo de Element

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

Então você pode começar a adicionar methods à sua class List. Aqui está um método “add” por exemplo.

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

usando:

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

Aqui está um com IEnumerable e um método Recursive Reverse embora não seja mais rápido que o while loop no método Reverse ambos são 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; } } 

Uma simples pesquisa no Google gerou este artigo:

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

parece bem simples à primeira vista …

Além disso, quando você estiver pronto para o próximo nível, use o refletor para examinar o LinkedList da própria Microsoft.

Aqui está uma boa implementação.

  1. É curto, mas implementou Add (x), Delete (x), Contain (x) e Print ().
  2. Evite processos especiais quando adicionar à lista vazia ou excluir o primeiro elemento. Enquanto a maioria dos outros exemplos fez processo especial quando excluir o primeiro elemento.
  3. A lista pode conter qualquer tipo de dados.

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

By the way, a implementação em http://www.functionx.com/csharp1/examples/linkedlist.htm tem algum problema:

  1. Delete () falhará quando houver apenas 1 elemento. (Lançamento exceção na linha “Head.Next = Current.Next;” porque atual é null.)
  2. Excluir (posição) falhará ao excluir o primeiro elemento. Em outras palavras, a chamada Excluir (0) falhará.

Eu estou dando um extrato do livro “C # 6.0 in a Nutshell por Joseph Albahari e Ben Albahari”

Aqui está uma demonstração sobre o 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; } } 

Testando com:

 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 fez um bom trabalho, mas aqui está uma versão mais 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; } } } 

Adicione uma class de nó.
Em seguida, adicione uma class LinkedList para implementar a linked list
Adicione uma class de teste para executar a linked list

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

simples programa c # para implementar Single Link List com operações AddItemStart, AddItemEnd, RemoveItemStart, RemoveItemEnd e 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(); } } } 

A resposta selecionada não possui um iterador; é mais básico, mas talvez não tão útil.

Aqui está um com um iterador / enumerador. Minha implementação é baseada na bolsa de Sedgewick; veja 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 classs 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() { } } }