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

And their principal pros/cons:

Quote

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:



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:



Functions:



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:




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!