Creating a very simple linked list

Question

I am trying to create a linked list to see if I can, and I am having problems with his head. Does anyone have an example of a very simple implementation of a Linked List using C #? All the examples that I have found so far are quite exaggerated.

Answer 1

A linked list, in essence, is a bunch of nodes linked together.

So, you need to start with a simple Node class:

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

Then your linked list will have as a member one node representing the title (start) of the list:

 public class LinkedList { private Node head; } 

Then you need to add functionality to the list by adding methods. They usually include some sort of crawl on all nodes.

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

In addition, inserting new data is another common operation:

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

This should provide a good starting point.

Answer 2

Based on what @jjnguy said and fixing the error in his PrintAllNodes (), here is an example console application:

 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

It's good:

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

Test code:

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

I came across this in msdn here

Answer 4

I am a newbie and it helped me:

 class List { private Element Root; } 

First, you create a List class that will contain all the methods. Then you create a Node-Class, I will call it Element

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

Then you can start adding methods to your List class. For example, the add method.

 public void Add(int value) { Element newElement = new Element(); newElement.Value = value; Element rootCopy = Root; Root = newElement; newElement.Next = rootCopy; Console.WriteLine(newElement.Value); } 

Answer 5

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

using:

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

Answer 6

Here is one of the IEnumerable and recursive inverse methods, although it is not faster than the while loop in the Reverse method - this is 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 7

A simple google search gave this article:

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

looks quite simple at first glance ...

Also, when you're ready for the next level, use a reflector to learn about Microsoft LinkedList.

Answer 8

Here is a good implementation.

• In short, Add (x), Delete (x), Contain (x) and Print () are implemented.
• It avoids the special process when adding to an empty list or deleting the first item. Although most other examples performed a special process when the first element was removed.

• The list may contain any type of data.

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

By the way, the implementation at http://www.functionx.com/csharp1/examples/linkedlist.htm have some problems:

• Delete () fails if there is only one item. (Throw an exception in the line "Head.Next = Current.Next;" because Current is null.)
• Delete (position) will not succeed when deleting the first element. In other words, the Delete (0) call will not be executed.

Answer 9

I give an excerpt from the book "C # 6.0 in a Nutshell by Joseph Albahari and Ben Albahari"

Here is a demo of using 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); 

Answer 10

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

Answer 11

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

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

Answer 12

Dmytro did a good job, but here's a shorter version.

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

Answer 13

Add a Node class.
Then add the LinkedList class to implement the linked list.
Add test class to execute 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(); } } } 

Answer 14

simple C # program for implementing Single Link List with AddItemStart, AddItemEnd, RemoveItemStart, RemoveItemEnd and DisplayAllItems operations

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

Answer 15

The selected answer does not have an iterator; this is more thorough, but perhaps not so useful.

Here is one with an iterator / enumerator. My implementation is based on a Sedgewick bag; see 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() { } } } 

Answer 16

I have created the following LinkedList code with many features. It is available to the public through the CodeBase github public repository .

Classes: Node and LinkedList

Getters and Setters: First and Last

Functions : AddFirst(data), AddFirst(node), AddLast(data), RemoveLast(), AddAfter(node, data), RemoveBefore(node), Find(node), Remove(foundNode), Print(LinkedList)

 using System; using System.Collections.Generic; namespace Codebase { public class Node { public object Data { get; set; } public Node Next { get; set; } public Node() { } public Node(object Data, Node Next = null) { this.Data = Data; this.Next = Next; } } public class LinkedList { private Node Head; public Node First { get => Head; set { First.Data = value.Data; First.Next = value.Next; } } public Node Last { get { Node p = Head; //Based partially on https://en.wikipedia.org/wiki/Linked_list while (p.Next != null) p = p.Next; //traverse the list until p is the last node.The last node always points to NULL. return p; } set { Last.Data = value.Data; Last.Next = value.Next; } } public void AddFirst(Object data, bool verbose = true) { Head = new Node(data, Head); if (verbose) Print(); } public void AddFirst(Node node, bool verbose = true) { node.Next = Head; Head = node; if (verbose) Print(); } public void AddLast(Object data, bool Verbose = true) { Last.Next = new Node(data); if (Verbose) Print(); } public Node RemoveFirst(bool verbose = true) { Node temp = First; Head = First.Next; if (verbose) Print(); return temp; } public Node RemoveLast(bool verbose = true) { Node p = Head; Node temp = Last; while (p.Next != temp) p = p.Next; p.Next = null; if (verbose) Print(); return temp; } public void AddAfter(Node node, object data, bool verbose = true) { Node temp = new Node(data); temp.Next = node.Next; node.Next = temp; if (verbose) Print(); } public void AddBefore(Node node, object data, bool verbose = true) { Node temp = new Node(data); Node p = Head; while (p.Next != node) //Finding the node before { p = p.Next; } temp.Next = p.Next; //same as = node p.Next = temp; if (verbose) Print(); } public Node Find(object data) { Node p = Head; while (p != null) { if (p.Data == data) return p; p = p.Next; } return null; } public void Remove(Node node, bool verbose = true) { Node p = Head; while (p.Next != node) { p = p.Next; } p.Next = node.Next; if (verbose) Print(); } public void Print() { Node p = Head; while (p != null) //LinkedList iterator { Console.Write(p.Data + " "); p = p.Next; //traverse the list until p is the last node.The last node always points to NULL. } Console.WriteLine(); } } } 

Using @yogihosting's answer when she used the built-in Microsoft LinkedList and LinkedListNode to answer the question, you can achieve the same results:

 using System; using System.Collections.Generic; using Codebase; namespace Cmd { static class Program { static void Main(string[] args) { var tune = new LinkedList(); //Using custom code instead of the built-in LinkedList<T> 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 Node miNode = tune.Find("mi"); //Using custom code instead of the built in LinkedListNode tune.Remove(miNode); // re - fa tune.AddFirst(miNode); // mi- re - fa } } 

Answer 17

A linked list is a node-based data structure. Each node is designed in two parts (link to data and nodes). In fact, data is always stored in a piece of data (perhaps primitive data types, for example, Int, Float.etc, or we can store a user-defined data type, for example, an object reference) and in a similar way. The link to the site must also contain a link to the next site. If there is no next node, the chain ends.

This chain will continue until any node has a reference point to the next node.

Please find the source code from my technical blog - http://www.algonuts.info/linked-list-program-in-java.html

 package info.algonuts; import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.List; class LLNode { int nodeValue; LLNode childNode; public LLNode(int nodeValue) { this.nodeValue = nodeValue; this.childNode = null; } } class LLCompute { private static LLNode temp; private static LLNode previousNode; private static LLNode newNode; private static LLNode headNode; public static void add(int nodeValue) { newNode = new LLNode(nodeValue); temp = headNode; previousNode = temp; if(temp != null) { compute(); } else { headNode = newNode; } //Set headNode } private static void compute() { if(newNode.nodeValue < temp.nodeValue) { //Sorting - Ascending Order newNode.childNode = temp; if(temp == headNode) { headNode = newNode; } else if(previousNode != null) { previousNode.childNode = newNode; } } else { if(temp.childNode == null) { temp.childNode = newNode; } else { previousNode = temp; temp = temp.childNode; compute(); } } } public static void display() { temp = headNode; while(temp != null) { System.out.print(temp.nodeValue+" "); temp = temp.childNode; } } } public class LinkedList { //Entry Point public static void main(String[] args) { //First Set Input Values List <Integer> firstIntList = new ArrayList <Integer>(Arrays.asList(50,20,59,78,90,3,20,40,98)); Iterator<Integer> ptr = firstIntList.iterator(); while(ptr.hasNext()) { LLCompute.add(ptr.next()); } System.out.println("Sort with first Set Values"); LLCompute.display(); System.out.println("\n"); //Second Set Input Values List <Integer> secondIntList = new ArrayList <Integer>(Arrays.asList(1,5,8,100,91)); ptr = secondIntList.iterator(); while(ptr.hasNext()) { LLCompute.add(ptr.next()); } System.out.println("Sort with first & Second Set Values"); LLCompute.display(); System.out.println(); } }