Basic Data Structures: Linked Lists
In a return to basics – and plenty of nothing to do – I implemented my own little linked list. Given the state of modern computing I have never really needed to implement a linked list, .Net framework has excellent libraries that manage lists and arrays, however, I guess it is always useful to understand the algorithms and foundations of computer science.
Lets start with what is a linked list:
A linked list is a data structure consisting nodes which together represent a sequence. Each node contains at least data and a reference to the next node. Hours and hours have been spent writing about linked lists, so no point on rehashing it again. For more information, you can use the Google machine or check Wikipedia’s page on the subject. http://en.wikipedia.org/wiki/Linked_list
Now the code
Declaring the node
Nothing fancy, straight forward thing
public class Node
{
public object data;
public Node next;
public Node(object data)
{
this.data = data;
}
}
Linked List
public class myLinkedList
{
public Node head;
Node current;
public void Add(Node n)
{
if (head == null)
{
head = n;
current = n;
}
else
{
current.next = n;
current = current.next;
}
}
public void InsertAtTop(Node n)
{
current = head;
if (n == null)
{
return;
}
n.next = current;
head = n;
}
public void Insert(Node n)
{
if (n == null) { return; }
if ((int)current.data >= (int)n.data)
{
n.next = current;
head = n;
return;
}
current = current.next;
while (current != null)
{
if ((int)current.data <= (int)n.data)
{
n.next = current.next;
current.next = n;
return;
}
current = current.next;
}
current.next = n;
}
public string ReverseAndParse()
{
string temp = “”;
current = head;
while (current.next != null)
{
temp = string.Concat(current.data.ToString(), temp);
current = current.next;
}
temp = string.Concat(current.data.ToString(), temp);
return temp;
}
public string Parse()
{
string temp = “”;
current = head;
while (current.next != null)
{
temp = string.Concat(temp, current.data.ToString());
current = current.next;
}
temp = string.Concat(temp, current.data.ToString());
return temp;
}
public void DisplayItems()
{
Node n = head;
while (n.next != null)
{
Console.WriteLine(“Node : {0}”, n.data);
n = n.next;
}
//display the lastone
Console.WriteLine(“Node : {0}”, n.data);
}
public void RemoveDuplicates()
{
current = head;
while (current.next != null)
{
Node n = current;
while (n.next != null)
{
if (n.next.data.Equals(current.data))
{
n.next = n.next.next;
}
else
{
n = n.next;
}
}
current = current.next;
}
}
public Node Split(object x, Node node)
{
Node ihead = node;
Node tail = node;
while (node.next != null)
{
Node next = node.next;
if ((int)node.data < (int)x)
{
node.next = ihead;
ihead = node;
}
else
{
tail.next = node;
tail = node;
}
node = next;
}
if ((int)node.data < (int)x)
{
node.next = ihead;
ihead = node;
}
else
{
tail.next = node;
tail = node;
}
tail.next = null;
this.head = ihead;
return ihead;
}
public Node addNodes(Node first, Node second, int CarryOver)
{
Node n = new Node(CarryOver);
int value = (int)(first == null ? 0 : (int)first.data) + (second == null ? 0 : (int)second.data) + CarryOver;
n.data = (value >= 10 ? (value – 10) : value);
if (first != null || second != null)
{
Node New = (addNodes((first.next == null ? null : first.next), (second.next == null ? null : second.next), (value / 10)));
if (New != null)
{
Add(New);
}
}
return n;
}
public Node BreakAndFix()
{
current = head;
Node breaker = current.next.next;
while (current.next != null)
{
current = current.next;
}
current.next = head.next.next;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if (slow.Equals(fast))
{
break;
}
}
if (fast == null || fast.next == null)
{
return null;
}
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
Serendipituos Code 
One thought on “Basic Data Structure: Linked Lists”