Linked list

A difficulty you may encounter with an array is that once an array is created, the size of that array is constant. So, if you use an array to store varying amount of data, you have to create an array which will be large enough. So, initially when the array does not contain much data, the allocated memory is unused. Also, you may not be able to determine the maximum amount of data you will have to store, thus the size of the array.

Linked lists can be used to solve this problem. Initially, the length of the linked list is 0. You can add data to the linked list as much as the available memory permits you.

This is a linked list which contains 3 nodes. In this linked list, nodes contain characters as data. the three nodes contain characters 'A', 'E', and 'Y'. Also, you can see that each node contains a pointer to another node. The pointer of the last node is NULL so that indicates there are no nodes next to it, thus it is the last.

Also, we need a way to find the first node. So, we use a node pointer "start", which stores the address of the first node. So, by that pointer, we can find the first node. From the next pointer of the first node, we can find the second node. From the next pointer of the second node, we can find the third node. By this way, we can traverse through the whole linked list.

Here is the structure which can be used as a node.

struct node
{
char data;
node *next;
};

We can create a class for implement the linked list.

class LinkedList
{
private:
node *start;
int length;

public:
LinkedList();      //constructor
~LinkedList();    //destructor

void Insert(char data);            //insert node at start
void InsertAt(int i, char data);   //insert node to given index
void Delete();                     //delete the first node of list
void DeleteAt(int i);              //delete the node at given index
void DeleteAll();                  //delete all the nodes
char Get();                        //get the first node data
char GetAt(int i);                 //get the data at given index
int GetLength();                   //get the length of the list
};

The given member functions are the basic functionality expected from a linked list. You can add more member functions according to your needs. Such as Find(), Sort() etc.

The constructor and destructor may look like this.

LinkedList::LinkedList()      //constructor
{
start = NULL;    //initially, the linked list should be empty
length = 0;}

LinkedList::~LinkedList()      //destructor
{
DeleteAll();}

When we need to add a new data (here, a character), it is easy to add it to the start of the list. Here is the procedure to add a new node at the beginning of the list.

1. Create a new node.
2. Put the data we need to add to the linked list to the data field of the node we created.
3. Put the content of the start pointer to the next pointer of the node, so it points to the Starting node of the linked list.
4. Put the address of our new node to the start pointer. So our new node becomes the first of the linked list.

Here is the function for add new data.

void LinkedList::Insert(char data)
{
node *n = new node;
n->data = data;
n->next = start;
start = n;
length++;}

Deleting data at the beginning of the list is also easy, as inserting to the beginning Here is the procedure to delete the first node.

1. Create a node pointer and give it the value of start pointer. So it is also pointing to the first node.
2. Put value of the next pointer of first node to start pointer. Then, first pointer points to the second node.
3. Delete the first node via the pointer created in step 1.

Here is the function for delete the first pointer.

void LinkedList::Delete()
{
if(length == 0)
return;            //we cannot delete if there is nothing
node *n = start;
start = start->next;
delete n;
length--; }

We can write the function DeleteAll() with the help of Delete().

void LinkedList::DeleteAll()
{
int l = length;
for(int i = 0; i < l; i++)
Delete();length = 0; }

The for loop in above function is executed for number of times equal to the number of nodes in the list. Each time the first node is deleted. So, after executing the loop, all the nodes are deleted. We have used a variable "l" instead of directly using "length" because in the loop, Delete() is executed and in Delete(), the length is reduced.

Lets look at a little longer function. Indexing is 0 based.

void LinkedList::InsertAt(int i, char data)
{
if((i > length)||(i < 1))
return;

node *n, *temp;
n = new node;
n->data = data;
temp = start;
for(int a = 0; a < (i - 1); a++)
temp = temp->next;
n->next = temp->next;
temp->next = n;
length++;}

This function inserts the given character to the given index of the linked list. First we have to deside which end is the starting of the list. That means we have to decide whether we consider the last item we put to the list is at the beginning of the list, or the first item is at the beginning. Above code is written considering the last item we entered is the 0 th of the list.

To understand the code, assume that i is 4. First we create a new node and put the data in it. Then, after the for loop is executed, our node pointer "temp" is pointing to the 3rd node. Then, we put the next pointer of "temp", which points to the former 4 th node, to our new node. Then we put the address of n to the third nodes next pointer. That means our new node becomes the fourth.

You may notice that if i is 0, there will be a problem. For simplicity, in the first line of the function, the function returns if i is 0, because there is another function which can be used easily to insert at position 0. You can fix that problem in this function without a problem if you clearly understood the concept.

You can download the source of the linked list as a header file here.