Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

An In Depth Look At Linked Lists

Icon 8 Comments
There are quite a few threads nowadays asking for assistance with linked lists. I find that the majority of these questions/problems/complications stem from a lack of understanding of the data structure itself. Why? Because (and this could just be me here) coding something is a non issue if I've worked out how the algorithm works, how the data is structured, the ins and outs, the hows and whys. Coding is the easy part. Programming is simply a tool by which to solve these types of problems (but I digress, more on this in another blog post I imagine).

Without any further ado:

Linked Lists

I can't think of a better generalized description, so I'll quote the linked list wiki page:

Quote

a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.


Posted Image

And their principal pros/cons:

Quote

The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations.

On the other hand, linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations such as obtaining the last node of the list, or finding a node that contains a given datum, or locating the place where a new node should be inserted may require scanning most of the list elements.


Why do I quote from the wiki? To save on time so we can get directly to the main point of this post--the example implementation!

I have made a templated example in C++ (Note: I have not included everything a list can do.). If you're not familiar with C++ or templates, that's ok, the concept of a linked list is the same regardless of specific language or feature implementation. Let your eyes glaze over the template<class T> portions :)

Note: The code is pretty much self explanatory, if I feel clarification is needed, there will be some (or code comments).

We have two classes, Node and LinkedList. The LinkedList consists of Nodes:

template<class T>
class Node {
private:
	T data;
	Node<T>* next;
public:
	Node();
	Node(T);
	T getData()					{return data;};
	Node<T>* getNext()			{return next;};
	void setNext(Node<T>*);
};



It's implementation:

template<class T>
Node<T>::Node() {
	data = NULL;
	next = NULL;
}

template<class T>
Node<T>::Node(T data){
	this->data = data;
	next = NULL;
}

template<class T>
void Node<T>::setNext(Node<T>* node){
	next = node; 
}



If you're more of a visual learner:

Posted Image

Each node holds its data and the next node in the list. Depending on where the node is in the list, it can be NULL.

In and of itself, this isn't very helpful, we need a container to hold them:

#include "Node.h"
template<class T>
class LinkedList {
private:
	Node<T>* head;
	Node<T>* curNode;
	Node<T>* tailNode; //used to make end insertion O(1) operation rather then O(n)
	int size;
public:
	LinkedList();
	LinkedList(T);
	~LinkedList();

	//functionality
	int getSize()				{return size;};
	void append(T);
	void displayAll();
	bool contains(T);
	void removeNode(T);
	T front()					{return head->getData();};
	T back()					{return tailNode->getData();};
};



The list keeps track of the head node (for pushing operations, not included here), the tail node (for O(1) appending, more on this later), the current node (a temporary handle that is reset and used for nearly every function, I find it more helpful then using "temp"), and its size. Every time a node is added or removed size is incremented or decremented respectively, this allows a constant check of the size of the list rather then a O(n) iteration to count the number of nodes.

Its implementation:

template<class T>
LinkedList<T>::LinkedList(){
	head = curNode = tailNode = NULL;
	size = 0;
}

template<class T>
LinkedList<T>::LinkedList(T element){
	Node<T>* temp = new Node<T>(element);
	head = temp;
	curNode = head;
	tailNode = head;
	head->setNext(NULL);
	size = 1;
}

template<class T>
LinkedList<T>::~LinkedList(){
	//iterate and free all the memory
	Node<T>* temp; //used for deletion
	curNode = head; //start at the beginning
	int counter = 0; //index tracker, for memory allocation checking
	if(head != NULL){
		do{
			//logging purposes
			cout << counter << " index freed" << endl;
			temp = curNode->getNext(); //get a handle to the next node
			delete curNode; //free current
			curNode = temp; //obtain the handle
			counter++;
			size--;
		}while (curNode != NULL);
	}
	else {
		cout << "List is empty, nothing to free" << endl;
	}

	cout << "Size (should be zero): " << size << endl;
}

template<class T>
void LinkedList<T>::append(T element){
	curNode = head; //start at the beginning
	Node<T>* temp;
	if(head != NULL){
		/* 
		******* O(n) method ************
		while(curNode->getNext() != NULL){
			//get to the end
			curNode = curNode->getNext();
		}
		********************************/
		//O(1) method
		temp = new Node<T>(element);
		tailNode->setNext(temp);
		tailNode = temp;
		cout << element << " successfully appended to the list!" << endl;
	}
	else {
		temp = new Node<T>(element);
		head = temp;
		head->setNext(NULL);
		tailNode = head;
		cout << "Default constructor used, " << element << " head successfully created!" << endl;
	}
	size++;
	return;
}

template<class T>
void LinkedList<T>::displayAll(){
	//O(n)
	curNode = head;
	cout << "Displaying list: " << endl;
	while(curNode != NULL){
		cout << curNode->getData() << " ";
		curNode = curNode->getNext();
	}
	cout << endl;
	return;
}

template<class T>
bool LinkedList<T>::contains(T element){
	//O(n) search
	curNode = head;
	while(curNode != NULL){
		if(curNode->getData() == element){
			return true;
		}
		curNode = curNode->getNext();
	}
	return false;
}

template<class T>
void LinkedList<T>::removeNode(T element){
	Node<T>* temp, *previous; //we'll need these later
	curNode = head; //default assignment
	//O(1) check (head node)
	if (head->getData() == element) { //remove head
		head = head->getNext();
		delete curNode;
		size--;
		cout << element << " was the head node, it was successfully removed" << endl;
	}
	else {
		while(curNode != NULL){
			//check data
			if(curNode->getData() == element){
				temp = curNode->getNext();
				if (temp == NULL){
					previous->setNext(NULL);
				}
				else{
					previous->setNext(temp);
				}
				delete curNode;
				curNode = temp;
				size--;
				cout << element << " a non head node, was successfully deleted!" << endl;
				break;
			}
			else {
				previous = curNode;
				curNode = curNode->getNext();
			}
		}
	}
}



Again, a visual representation:

Constructors/Destructor:

Posted Image

Functions:

Posted Image

I've included Big O comments in many of the functions, indicating why a particular solution is more efficient then another. for example, if we did not keep track of the tail node, we'd have to iterate to the end to append a node which makes a constant O(1) operation a linear one. If you're just starting out, you probably don't give two shits about Big O or efficiency, but it's good to know for later. There's also many places where I left tracer statements so you could see what was going on in the console. i.e. if a head node was removed, a regular node, so on and so forth.

The destructor is of particular importance, it will free all allocated memory the list has. It does this by starting at the head node, assigning the value of curNode->getNext() to a temp holder and then deleting curNode. If we did not do this, we'd have a memory leak. If you deleted the node before getting a handle to its next value, you have broke the chain and will be leaking memory. A quick way to check to make sure we have cleaned up is to check size at the end of the destructor, if it's not zero then we messed up in our clean up or forgot a size++/size-- somewhere.

An example main:

#include <iostream>
#include <string>
#include "LinkedList.h"
using namespace std;

int main() {
	
	LinkedList<string>* anotherList = new LinkedList<string>();

	anotherList->append("Bob");
	anotherList->append("Knowles");
	anotherList->append("Mary");
	anotherList->removeNode("Knowles");
	anotherList->displayAll();

	delete anotherList;
	

	return 0;
}



Example output:

Posted Image


Compilation notes:
>Templates require the implementation to be in the same file as the declaration, so no separate matching header/cpp files


Hopefully you found this helpful. As previously mentioned I did not make a fully robust list (in the sense that there are functions I could add, like pushing a node on the top). And I'm sure there are things I could make more efficient. I did make all the pictures from scratch though. Happy coding!

8 Comments On This Entry

Page 1 of 1

Smurphy Icon

27 October 2009 - 05:05 PM
Nice post. We went over this a few weeks ago in my computer science class. I know many people had a lot of trouble wrapping their minds around a linked list, including myself at first. This was a great break down, with the pictures and all. which was what helped me. Except I wrote it on a piece of paper completely illegibly and my mumblings scared the family. Thanks again KYA.
0

KYA Icon

27 October 2009 - 05:14 PM
Glad you liked it

I mumble to myself when I'm writing/coding too :)
0

Martyr2 Icon

27 October 2009 - 06:20 PM
Just wanted to say this is a pretty bad ass post. It is good to see someone putting together a great blog entry. Keep up the good work. :)
1

Locke Icon

28 October 2009 - 10:02 PM

Martyr2, on 27 Oct, 2009 - 07:20 PM, said:

Just wanted to say this is a pretty bad ass post. It is good to see someone putting together a great blog entry. Keep up the good work. :)


Yeah, that. :D

I also had trouble with linked lists (as you may remember, KYA, you helped me with my first project on 'em ;)), and I can see how this would be a GREAT resource. :^:
0

david.bobrowski Icon

03 December 2009 - 10:05 PM
This post was extremely helpful...thank you so much.
0

NickDMax Icon

11 December 2009 - 02:20 PM
You know I just did a linked list here and it made me realize that your class is missing 2 things that are actually kind of important:

A copy constructor and and an assignment operator. I think you will find that as you try to use your class some problems arise without these two items. I would not say they are "Required" but the general rule of thumb is: if you need 1 you need all 3.
0

KYA Icon

11 December 2009 - 02:37 PM
Not necessarily. In the above post, I didn't do any direct assignment or copying between two list objects. I did end up writing them later though for personal use.


edit: Clarification: They should be there, however, I intentionally omitted them since I was only doing examples of single list construction.
0

Kutlar Icon

21 December 2010 - 05:54 PM
Very good stuff!
0
Page 1 of 1

August 2014

S M T W T F S
     12
3456789
10111213141516
1718192021 22 23
24252627282930
31      

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)