A linked list is a type of dynamic data structure that consists of nodes linked together. Each node contains two parameters, data and the address of the next node.

Properties

Head

The head is a property of a linked list that represents the first node in the list. When accessing elements the head node is the first one (ie arr.get(0)).

Tail

The tail is a property of a linked list that represents the last node in the list.

Abstract Data Type

We can define a linked list abstractly as follows:

template <class T>  
struct Node {  
	T data;  
	Node * next;  

	Node(LIT ndata, Node * nx=nullptr): data(ndata),next(nx) {}  
};

template <class T>
struct LinkedList {
	private:
		Node* head;
		Node* tail;
		
		int length;
		
	public:
	 LinkedList();
	 
	// ... Ommited
}

Auxiliary Operations

Traversing a Linked List

To traverse a linked list maintain a pointer to the current node dereferencing it each iteration, if the next parameter of the node is NULL, the whole linked list has been traversed, otherwise update the pointer to the current node to be the next parameter.

Example

void iterateLinkedList(Node<int>* startingNode) {
	Node<int>* p = startingNode;
	
	while (p->next != nullptr) {
		std::cout << p->data << std::endl;
	
		p = p->next;
	}
}

Inserting into a Linked List

To insert into a linked list maintain a pointer to the node to insert, and a pointer to the node before and after the node to insert, then just set the next parameter of the node before to be the address of the node to insert, and the next parameter of the node to insert to be the node after the node to insert.

Example

void insertNodeIntoLinkedList(
	Node<int>* previousNode,
	Node<int>* nextNode,
	Node<int>* newNode
) {
	previousNode->next = newNode;
	newNode->next = newNode;
}

Deleting from a Linked List

To delete from a linked list set the previous node's next to be the node after the one to delete, and then free the memory of the node to delete

Example

void deleteNodeFromLinkedList(
	Node<int>* previousNode,
	Node<int>* nodeToDelete,
	Node<int>* nextNode
) {
	previousNode->next = nextNode;

	delete nextNode;
}

Time Complexity

Operation	Time Complexity
Insertion at Beginning
Insertion at End
Insertion at Position
Deletion at Beginning
Deletion at End
Deletion at Position
Searching for Element

Without Tail Pointer

Operation	Time Complexity
Insertion at End