Linked Lists are a data structure that are based on sequential order of items like an array but they are more robust and efficient in terms of insertion, deletion of items at any given place inside of the linked list.
In order to insert an item in to an array at the beginning of the array, we have to shift all the items from index 0 … N, where N is the size of the array which has a time complexity of O(N). These matter significantly when N gets very large. But in linked list it is a matter of rearranging some pointers/references of nodes which has a time complexity of O(1). It cannot get better than that.
Therefore linked lists are perfect candidate for data that needs to be stored in the order they are received.
For example, if you want to store bank transactions in the order you received them and retrieve them back when needed, we can leverage the power of linked list.
Linked list node has basically two things. One the data it stores and two a reference of the node that is next/previous to it.
The data can be of any data type like int , datetime, double, stack etc. We can store on or more variables in here to represent our data.
The reference is an object of the same type the linked list class is defined. For example, if the linked list data structure we want to represent is called Transaction, then we as part of our reference to the next node, we can use Transaction as a data type for this pointer.
Linked list has a head and tail. Head is the first node whereas tail is the last node.
Linked list can be unidirectional (singly linked list) or bi-directional (doubly linked list).
Singly linked list
Singly linked list contains node(s) that store a reference of a node to only what is next to it.
class Solution {
static void Main(string[] args) {
SinglyLinkedList slist = new SinglyLinkedList();
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
slist.Insert(node1);
slist.Insert(node2);
slist.Insert(node3);
slist.Display();
}
public class SinglyLinkedList {
public Node head;
public SinglyLinkedList() {
}
public void Insert(Node n) {
if(head == null)
head = n;
else {
Node iter = head;
while(iter.next!=null) {
iter = iter.next;
}
iter.next = n;
}
}
public void Display() {
Node iter = head;
while(iter!=null) {
Console.WriteLine(iter.val);
iter = iter.next;
}
}
}
public class Node {
public Node next;
public int val;
public Node() {
}
public Node(int val)
{
this.val = val;
}
}
}
Doubly linked list
Doubly linked list contains node(s) that store a two references of a node to what is next to it and what comes before it.
Let define our first linked list.
public class Transaction{
public DateTime? Date { get; set; }
public double Amount { get; set; }
public Transaction Next { get; set; }
public Transaction Previous { get; set; }
public Transaction(DateTime? date, double amount){
this.Date = date;
this.Amount = amount;
}
public override string ToString() {
return "Transaction Date: " + Date + "\n\t" + "Transaction Amount: " + "$" + Amount;
}
public void Print() {
Console.WriteLine(ToString());
}
}
Here we define a doubly linked list that has two types of data we want to store transaction date and amount, and also we keep a reference of the next and previous nodes to this node. This is just a blue print of what we are going to do in the next phase where we actually use it.
Now let's see how we can actually use this linked list.
Transaction History table we can create a transaction linked list using the default constructor.
In the default constructor we will create two empty head and tail nodes but we link them together by making tail's next node to be head node and head's previous node to be tail node.
Head → ←Tail
Every time we add a new transaction we will create a new node with data (transaction date and amount). Then we will take care of the order in which the node is inserted. We have to make sure new nodes are inserted at the end of the linked list (before the empty tail). It is like first come first served. When we display them we go in the order from head to tail.
Assume you have a chain of nodes like this.
Now let's say we want to add a new node just after the First Node
| Head → | ← First → | ← New → | ←Tail |
We need to do the following:
- Set new node's next reference to the tail. New →
- Set new node's previous reference to the tail's previous ← New
- Overwrite the next reference of the First node with the new Node. But this change based on how many node we have. If we have First and Second Nodes this will change to set it to Second node next should be new node, if there is third node, then third node next should be new node… So the trick here is to set tail's previous next node to be the new node as tail's previous would simply means First or Second or Third node depending the size of your linked list. Head→ or First → or Second → etc.
- Overwrite the previous reference of the Tail node with the new node. ←Tail
public class TransactionHistory {
private Transaction Head { get; set; }
private Transaction Tail { get; set; }
TransactionHistory(){
Head = new Transaction(null, 0.0);
Tail = new Transaction(null, 0.0);
Head.Next = Tail;
Tail.Previous = Head;
}
public void AddTransaction(double amount) {
Transaction NewTrans = new Transaction(DateTime.Now, amount);
NewTrans.Next = Tail;
NewTrans.Previous = Tail.Previous;
Tail.Previous.Next = NewTrans;
Tail.Previous = NewTrans;
}
public void Print() {
Transaction current = Head.Next;
while (current != Tail) {
current.Print();
current = current.Next;
}
}
public double Balance() {
Transaction current = Head.Next;
double balance = 0;
while (current != Tail) {
balance += current.Amount;
current = current.Next;
}
return balance;
}
}
public static void Main(string[] args) {
TransactionHistory transHistory = new TransactionHistory();
transHistory.AddTransaction(100);
Thread.Sleep(1000);
transHistory.AddTransaction(-200);
Thread.Sleep(1000);
transHistory.AddTransaction(300);
Thread.Sleep(1000);
transHistory.AddTransaction(400);
Thread.Sleep(1000);
transHistory.Print();
Console.WriteLine(transHistory.Balance());
}
Output:
Transaction Date: 10/15/2011 6:53:37 PM
Transaction Amount: $100
Transaction Date: 10/15/2011 6:53:38 PM
Transaction Amount: $-200
Transaction Date: 10/15/2011 6:53:39 PM
Transaction Amount: $300
Transaction Date: 10/15/2011 6:53:40 PM
Transaction Amount: $400
600