Data Structures - Linked Lists

Linked lists are probably the simplest data structure of all. They are just nodes, containing some data and a reference to the next node in the list, all nodes are linked to one other node and they form a sequence or a list. This is the most basic form, we’ll talk about some other ones later.

We talked already about arrays so lets compare the two and see why one may be better than the other.

Advantages of arrays

  • cache locality, since all the elements are in contiguous locations locality of reference is better
  • random access, you can access an element by it’s index so it doesn’t matter if it’s the first, last or in the middle
  • Elements take less memory since there is no need to store a pointer to the next other elements

Advantages of linked lists

  • Dynamic size, since the elements aren’t all stored as they are in arrays, there is no need to allocate memory in advance irrespective of if all the space is being used or not
  • Because of dynamic size inserting and deleting elements is really easy, which is not the case with arrays since expanding or shrinking is expensive

Implementation

As I said linked lists are not stored as arrays, all elements in on container. Linked list is represented by the first value, called head, it stores a pointer to the next node, that one points to the third and so on.

Since the implementation and methods of linked lists are so simple I’ll be covering only the C++ implementation for other languages there will be a link to my GitHub repo:

class Node
{
public:
		int Data;
		Node* next;
};

Methods of a linked list

Next we’ll look at how to initialize, traverse, insert and delete elements in linked lists. Inserting has a time complexity O(1), inserting O(1) if we provide the pointer to the node after which we need to insert, else it can be at worst O(n) time, deleting always takes O(n) time.

class Node
{
public:
		int data;
		Node* next;
};

int main()
{
		//Creating nodes manually
		Node* head = new Node();
		Node* second = new Node();
		Node* last = new Node();
		
		//Assiging values
		head->data = 1;
		head->next = second;
		
		second->data = 2;
		second->next = last;
		
		last->data = 3;
		last->next = nullptr;
		
		//Using a for loop to create a linked list
		Node* head = new Node();
		Node* current = head;
		for(int i = 0; i < 10; i++)
		{
				Node* newNode = new Node();
				newNode->data = i
				current->next = newNode;
				current = newNode;
		}

		//Traversing is done with a while loop
		//Last node will always point to nullptr
		//So that's our break condition
		while(current->next != nullptr)
		{
				current = current->next;
				//Do something
		}

		//Inserting can be done three ways
		//to the first position, last
		//and somewhere in the middle

		/*When adding at the first spot
			- make current head the next to the new node
			- new node becomes a new head
		*/
		void push(Node* head, int data)
		{
				Node* newNode = new Node();
				newNode->data = data;
				
				newNode->next = head;
				head = newNode;
				
				return;
		}
		/*When inserting 
			- we need a previous node
			- make new node point to it's next
			- set previous point to the new node
		*/
		void insert(Node* prevNode, int data)
		{
				Node* newNode = new Node();
				newNode->data = data;
				
				newNode->next = prevNode->next;
				prevNode->next = newNode;
				
				return
		}
		/*When adding at the end we need to taverse the whole list
			- new node is the new end so it points to null
			- last node now points to the new one
		*/
		void append(Node* head, int data)
		{
				Node* newNode = new Node();
				newNode->data = data;
				newNode->next = nullptr;
				
				if(head->next == nullptr)
				{
						head->next = newNode;
						return;
				}
				Node* current = head;
				while(current->next != nullptr)
				{
						current->next;
				}
				current->next = newNode();
				return;
		}
		return 0;
}

Deleting can be done in two ways, by traversing a list to find the value or by recursively searching for the key.

Deleting checklist:

  • Find the previous node to one we’re deleting
  • Change it’s next pointer
  • Free up memory

We also need some way to know which node to delete. Here I’ll use the data as a key

//inside node class
	
void deleteNode(Node* head, int key)
{
		Node* temp = head;
		Node* prev = nullptr;
		// If head is to be deleted
		if(temp != nullptr && temp->data == key)
		{
				head = temp->next;
				delete temp;
				return;
		}
		//In recursive method here would be a call to delete
		//deleteNode(head->next, key)
		
		// Search for the key to be deleted
		while(temp != nullptr && temp->data != key)
		{
				prev = temp;
				temp = temp->next;
		}

		if(temp == nullptr){ return; }
		
		prev->next = temp->next;
		delete temp;
		
		return;
}

Other Types – Doubly Linked and Circular Linked List

Up until this point we looked at a type of LL called singly linked. This means each node points to it’s next and that’s it. Doubly linked lists have a reference to the previous node as well as the next one. They are used to maintain references to some dynamic objects.

Circular linked lists aren’t a different type but a different way to end one. Usually last node in the list points to null, this is called open or linear, but in this case it points back to the head creating a circle.

That was the overview of linked lists, next time we’ll cover hash tables and see how linked lists are used to implement one.

Archives
Recent Posts