Data Structure & Algorithms

• Node (value | next-pointer)
• Node Chains (two/more nodes connecting with help of next-pointers)

public class Node
{
  public int Value { get; set; }
  public Node Next { get; set; }
}

Node first = new Node { Value = 3 };
Node middle = new Node { Value = 5 };
first.Next = middle;
Node last = new Node { Value = 9 };
middle.Next = last;

Linked List

• Single chain of nodes
• Head Pointer
• Tail Pointer
• Operations: Add, Remove, Find, Enumerate
  • If there is only one item in the list, then both head and tail pointers will point to single node
  • Adding: Will update the head/tail pointer and the corresponding next-pointer (in case of array there will be performance impacts ex: adding a new value at the beginning will have to shift all the other values by one step)
• Doubly Linked List: .Net's linked list is Doubly Linked List

Stack (LIFO)

• Push & Pop
• Linked list can be used for stacking
  • Pros: No hard size limit. No bounds check (as in case of array)
  • Cons: memory allocation push, per node memory overhead, performance issues
• Linked List Implementation of stack
• Array Implementation of stack
• Always best to use the Stack that comes in the framework ((C# Stack)[https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/stack.cs] - stores in array)
• Stack Usages:
  • Undo operation
  • compiler's syntax check for matching braces is implemented by using stack
  • During Function Calls because it Follows A LIFO Structure
  • Back/Forward stacks on browsers

SOURCES

• My Own Github