Linked List(part 1)

Linked Lists, every Data Structures student nightmare. But it shouldnt be because the concept is easy to grasp.  The main idea is that a linked list is a list of nodes linked together, as it’s name implies. So, each node has a value and a pointer to the next node in the series.

How do we know where the list ends? The tail node, the last node in the series, points to NULL, or 0 (zero).

Lets start some coding, shall we:

class LinkedListNode
{
public:
	int data;
	LinkedListNode *next;

	LinkedListNode()
	{
		data=0;
		next=NULL;
	}
	void setData(int value)
	{
		data = value;
	}
	int getData()
	{
		return data;
	}
};

The LinkedListNode class holds an integer, you could make this any data type of your choice but i’m using an integer for example purposes, and a pointer to the next node. In the constructor we initialize the values of each data type; we set ‘data’ to 0 and the pointer ,next, to NULL. A NULL ‘next’ pointer means that that node is the end of the list, other than that it’s good to initialize pointers to NULL, or 0, so u wont modify any unallocated data in memory, worst case data from another application. getData and setData is just a getter and a setter for dat’.

class LinkedList
{
	LinkedListNode *head;
public:
	LinkedList()
	{
		head=0;
	}
	void addFront(int value)
	{
	}
	LinkedListNode *getHead()
	{
		return head;
	}
};

This is our linked list class. It holds the first node in the series in the variable ‘head’. The constructor initializes ‘head’ to null, this means that there is nothing in the list as yet. The ‘getHead()’ function is a getter for head. addFront(int value) adds a node to the front of the list and getSize() gets its size.

Adding nodes to the list

Here we’ll be adding an element to the front of our list. First of all, we create the node and set the value

LinkedListNode *node = new LinkedListNode();
node->setData(value);

Now, if the list is empty,head==NULL, then we make our newly created node be the head by default.

if(head==NULL)
{
	head=node;
}

If not, then we have a little shifting around to do. We have to make the new node be the head, and make it point to the old head. In actuality we do this in reverse.

else
{
	node->next=head;
	head=node;
}

We’re almost done. We have to count the elements in the list now. Here we have to use a while loop.

    int getSize()
	{
		int size=0;
		LinkedListNode *node=head;

		while(node!=NULL)
		{
			size+=1;
			node = node->next;
		}

		return size;
	}

we set ‘size’ to 0 by default. Then we set out temporary node to point to the head. In our loop, as long as the node isnt 0, size is incremented and node is pointed to the nest node in the series.

lets see if i can explain wat happens with 2 scenarios:

Scenario 1:

lets say the list is empty, this would mean that head==NULL. The code in the loop wont execute since it’s condition isnt met which is “node!=NULL”, meaning node should not be equal to NULL. So that function will return 0;

Scenario 2:

lets say we have 2 nodes in the list. The code in the loop will be executed twice; the first time  for the head and the second time for the head’s next pointer.

Hope that helped.

We’re done already, but  this is just part 1 anyway :P.

Now lets test this 😀

    LinkedList list;
	list.addFront(5);
	list.addFront(10);
	list.addFront(15);
	list.addFront(20);

Now iterate through and display the contents of each node:

    LinkedListNode *node = list.getHead();
	while(node!=NULL)
	{
		cout<<node->data<<endl;
		node = node->next;
	}

Here is a screenshot of the results:

The numbers are displayed in reversed because addFront() adds elements to the front of the list not the end

If you’re lazy then u can get back to browsing on facebook feeling satisfied with ur self. if you’re not then lets move on to one final step; cleaning up after ourselves.

Remember when u were a baby and you played with your toys and u didnt have to put them back because your mom would. Then when u got older u had to put back watever toy u took out in the toy box. In that analogy, the toy box in your RAM, the toy in the amount of memory you take when u make a variable and your mom is C++. When u create a variable in c++ and it goes out of scope the memory is deallocated for you, so u dont have to worry about a thing besides using the variable( playing with your toys)

class MyClass
{
};

MyClass instance;

But you’re a big kid now, you use pointers. When creating a pointer to an instance of a class we do this

MyClass *instance;

And instantiate the class with the ‘new’ operator like so:

MyClass *instance = new MyClass();

When u do that C++ isnt responsible for deallocating that memory u allocated with the ‘new’ pointer. The size of the instance depents on the total size of each data member of the class. So when we’re done with the instance, we use the ‘delete’  operator to free the memory, the destructor of the instance also called when doing this.

delete *instance;

Now let’s take this to our class’ destructor.

    ~LinkedList()
	{
		//delete nodes here
		LinkedListNode *node=head;
		while(node!=NULL)
		{
			LinkedListNode *tmp = node->next;
			delete node;
			node= tmp;
		}
	}

We iterate through nodes and delete each, freeing the memory we allocated when we created them. We put this code in our destructor so when our LinkedList goes out of scope the destructor is called which frees the memory.

and finally we’re done 😀

Here’s the entire source code:

#include <iostream>

using namespace std;

class LinkedListNode
{
public:
	int data;
	LinkedListNode *next;

	LinkedListNode()
	{
		data=0;
		next=NULL;
	}
	void setData(int value)
	{
		data = value;
	}
	int getData()
	{
		return data;
	}
};

class LinkedList
{
	LinkedListNode *head;
public:
	LinkedList()
	{
		head=NULL;
	}
	void addFront(int value)
	{
		LinkedListNode *node = new LinkedListNode();
		node->setData(value);

		if(head==NULL)
		{
			head=node;
		}
		else
		{
			node->next=head;
			head=node;
		}
	}
	int getSize()
	{
		int size=0;
		LinkedListNode *node=head;

		while(node!=NULL)
		{
			size+=1;
			node = node->next;
		}

		return size;
	}
	LinkedListNode *getHead()
	{
		return head;
	}
	~LinkedList()
	{
		//delete nodes here
		LinkedListNode *node=head;
		while(node!=NULL)
		{
			LinkedListNode *tmp = node->next;
			delete node;
			node= tmp;
		}
	}
};

int main()
{
	LinkedList list;
	list.addFront(5);
	list.addFront(10);
	list.addFront(15);
	list.addFront(20);

	//iterate through list
	LinkedListNode *node = list.getHead();
	while(node!=NULL)
	{
		cout<<node->data<<endl;
		node = node->next;
	}

	system("pause");
	return 0;
}

i’ll put up part 2 next week. I’ll be adding a tail to our linked list and a addBack frunction. Happy coding until then 😀

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s