Hi I would like to start the series about data structures with LinkedList. LinkedList problems is very popular interview questions. So you have to know the basics of the LinkedList really well.
So # 1 What is LinkedList?
Wikipedia: “In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence.”
wiki.answers.com Another explanation: LinkedList is a set of elements, usually structures, where each element contains a pointer or index to the “next” element, along with the data represented by the element.
Simple explanation: LinkedList is a data structure that is used to store sequence of elements. Each element is stored in the “node”. Each “node” has a pointer to next “node”.
Ok, so what would the linked list with numbers 4,5,1,9 look like:
Every box is a Node with number; the arrow represents the pointer to the “next” node. The last node will always point to null
# 2 How LinkedList stores sequence of elements?
It creates an own node for each element; this node holds the actual element and a pointer (reference) to the next node. The elements this way can be spread all over the memory and are not stored at specific memory locations. That’s why lists are not limited in size but for the amount of available memory.
# 3 What are the advantages of using LinkedList?
- Its best to use LinkedList when you don’t know in advance the number of elements you have to store. LinkedList is not a fixed size like array.
- Easy to insert or delete nodes with elements without fixing its size in the memory. Since linkedlist uses as much memory to store items as it needs.
Implementation of the LinkedList (C#)
public class Node
{
private int _number;
private Node _next;
public Node(int number)
{
_number = number;
}
public Node Next
{
get { return _next; }
}
public int Number
{
get { return _number; }
}
public void AppendToTail(int data)
{
Node n = this;
while (n.Next != null)
{
n = n.Next;
}
n._next = new Node(data);
}
}
