LinkedList is a common data structure being used. One of the difference between linked list and array based structures are, linked list doesn’t require contiguous memory space. Moreover, expansion within array based data structures bases on a load factor that s determined by the engineers who build the structures, and expansion of arrays usually twice the size of the current size. During expansion of the array, CLR creates a new array with the new size and then copy all the entities from one array to another. Even though this seems to be a an easy operation, as you data grows, it might become slow. Imagine, your array size becomes 5 million elements, next expansion would require contiguous memory to hold 10 million blocks. So this operation becomes very expensive. Benefit of linked list in the aspect is that, it doesn’t require contiguous memory space, nodes can be anywhere withing the Virtual Memory. Since we keep pointers to the nodes, that is sufficient to access any node which is linked by another node. Therefore the issue we mentioned above doesn’t happen with linked list.
There can be several algorithms and problems based on linked list due to the fact that linked list is convenient for multiple pointer usages, recursion, iteration, reversing etc.
Some of the examples are follows and the best way to practice them is to write code for it after understanding them.
If there is a cycle in a given linked list, you can find it by marking the visited nodes as visited, if you see a visited node again, you halt. This solution requires you to modify the Node structure and add a bolean to it. Another solution would be to have two pointers at the beginning, one that moves one by one node, and another pointer, that moves 2 nodes at a time. And if there is a cycle in the linked list they will meet both pointers will eventually meet.
A way to find out the middle element of a linked list is to use two pointers, one that moves one by one and another that moves two by two. Once the one that moves two nodes at a time reaches to the end, first node comes to the middle of the linked list.
To check if a given linked list is palindrome, divide the list into two parts. Reverse the first part and compare with the second part node by node. If they are equal that, linked list contains a palindrome. There are several different approaches to solve palindrome problem both recursively and iteratively.
Given two singly linked lists in sorted order, which forms a Y shape, you can reverse both of the linked lists and compare each element one by one by keeping two pointers. Once you reach the nodes that don’t intersect. Previous nodes are the intersection points.
Given a sorted singly linked, it s possible to remove the duplicates with a single iteration, by keeping two pointers, one to current node and one to the next node. If the next node is equal to current node, connect the current node to next node’s next node.
Given an unsorted singly linked list, it s possible to remove duplicates by using a dictionary. Store elements in the dictionary as you iterate the list. Each time you move to a node, check the dictionary, if the element is in the dictionary already, that s duplicate. Another way is to sort and do the above algorithm.
Given a linked list of even and odd numbers, you can separate the even numbers from the odd ones as follows. Using two pointers, one to point to the head and another to point to the tail, start iterating from both ends, if first pointer’s node is even and second pointer node is odd then swap them. Otherwise keep moving the pointers until you reach a odd or even number. Then swap them until two pointers overlap.
Given a linked list in which you need to set the last node as the head of the linked list. You traverse the linked list once. Once you reach to the end, you also keep a previous pointer to find the node that will qualify to last node. Last node next pointer will be assigned to the head pointer and then will qualify to be the head node. Tail node will be the second pointer node, whose next pointer will point to null.
Below is an implementation of a linked list that I have quickly written. Syntax hightlighter is not working perfect as you can see. Sorry about that.
using System;
using System.Collections;
using System.Collections.Generic;
namespace FiratAtagun.DataStructureTests.LinkedList
{
public class Node : IEquatable where T : IComparable
{
public Node Next;
public Node()
{
}
public Node(T data)
{
Data = data;
}
public Node(Node data)
{
Data = data.Data;
}
public Node(T data, Node next)
{
Data = data;
Next = next;
}
public T Data { set; get; }
#region IEquatable Members
public bool Equals(T other)
{
return Data.Equals(other);
}
#endregion
}
public enum InsertionMethod
{
Default,
Recursive,
Iterative
}
public class SinglyLinkedList : ICollection> where T : IComparable
{
private int _count;
private Node _head;
private Node _iterator;
public SinglyLinkedList()
{
}
public SinglyLinkedList(T data)
{
_head = new Node(data);
}
public SinglyLinkedList(Node node)
{
_head = node;
}
public SinglyLinkedList(IEnumerable collection)
{
foreach (T item in collection)
{
Insert(item);
}
}
#region ICollection> Members
public void Add(Node item)
{
Insert(item);
}
public void Clear()
{
_head = null;
}
public bool Contains(Node item)
{
Node found = Find(item);
return found != null ? false : true;
}
public void CopyTo(Node[] array, int arrayIndex)
{
throw new NotImplementedException();
}
public int Count
{
get { return _count; }
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(Node item)
{
return Delete(item);
}
public IEnumerator> GetEnumerator()
{
_iterator = _head;
while (_iterator != null)
{
yield return _iterator;
_iterator = _iterator.Next;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
public void Insert(T data, InsertionMethod insertionMethod = InsertionMethod.Default)
{
_count++;
Insert(new Node(data), insertionMethod);
}
public void Insert(Node node, InsertionMethod insertionMethod = InsertionMethod.Default)
{
if (insertionMethod == InsertionMethod.Default || InsertionMethod.Iterative == insertionMethod)
{
InsertIteratively(node);
return;
}
InsertRecursively(node);
}
private void InsertRecursively(Node node)
{
if (_head == null)
{
_head = node;
return;
}
Node currentNode = _head;
InsertRecursively(node, currentNode, null);
}
private void InsertRecursively(Node node, Node currentNode, Node previousNode)
{
if (currentNode != null)
{
InsertRecursively(node, currentNode.Next, currentNode);
return;
}
currentNode = node;
previousNode.Next = currentNode;
}
private void InsertIteratively(Node node)
{
if (_head == null)
{
_head = node;
return;
}
Node currentNode = _head;
while (currentNode.Next != null)
{
currentNode = currentNode.Next;
}
currentNode.Next = node;
}
public bool Delete(Node node)
{
return true;
}
public Node Find(T element)
{
foreach (var item in this)
{
if (element.Equals(item.Data))
return item;
}
return null;
}
public Node Find(Node node)
{
foreach (var element in this)
{
if (node.Data.Equals(element.Data))
return element;
}
return null;
}
public void InsertAfter(T data, Node node)
{
}
public void InsertBefore(T data, Node node)
{
}
public bool Replace(T data, Node node)
{
return true;
}
public bool Contains(T item)
{
return Contains(new Node(item));
}
}
}
Not logged in