Doubly Linked List

Doubly Linked List

A doubly linked list whose nodes contain three fields

1. data
2. the pointer to the previous node
3. the pointer to the next node

WIKIPEDIA - Doubly linked list

Time complexity

\(n\) : the number of nodes

• insert new node: \(O(1)\)
• append new node: \(O(1)\)
• delete \(i\)th node \((0 \le i \lt n)\)
  • forward and backward : \(O(1)\)
  • others : \(O(n)\)
• delete a pointer to the node that is given : \(O(1)\)
• find
  • forward and backward : \(O(1)\)
  • others : \(O(n)\)
• traversal : \(O(n)\)

header

//
//  DoublyLinkedList.hpp
//  c++
//

#ifndef DoublyLinkedList_hpp
#define DoublyLinkedList_hpp

#include <iostream>

template<typename T>
struct Node {
	T data;
	Node *prev, *next;
	
	Node() : data(NULL), prev(nullptr), next(nullptr) {}
	Node(T data) : data(data), prev(nullptr), next(nullptr) {}
};

template<typename T>
class DoublyLinkedList {
private:
	Node<T> *head = nullptr, *tail = nullptr;
	int _size = 0;
	
public:
	// insert data at the beginning of the list
	void insert(T data);
	
	// append data at the end of the list
	void append(T data);
	
	// remove data from the list
	void remove(T data);
	
	// return the size of the list
	bool isEmpty();
	
	// return the size of the list
	int size();
	
	// print all data in the list
	void printAll();
};

#endif /* DoublyLinkedList_hpp */

implementation

//
//  DoublyLinkedList.cpp
//  c++
//
//

#include "DoublyLinkedList.hpp"

template<typename T>
void DoublyLinkedList<T>::insert(T data) {
	Node<T> *newNode = new Node<T>(data);
	if(head == nullptr) {
		head = tail = newNode;
	} else {
		newNode->next = head;
		head->prev = newNode;
		head = newNode;
	}
	_size++;
}

template<typename T>
void DoublyLinkedList<T>::append(T data) {
	Node<T> *newNode = new Node<T>(data);
	if(head == nullptr) {
		head = tail = newNode;
	} else {
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
	_size++;
}

template<typename T>
void DoublyLinkedList<T>::remove(T data) {
	Node<T> *current = head;
	while(current != nullptr && current->data != data) 
		current = current->next;
      
	if(current == nullptr) return;
	
	if(current == head) {
		head = head->next;
		head->prev = nullptr;
	} else if(current == tail) {
		tail = tail->prev;
		tail->next = nullptr;
	} else {
		current->prev->next = current->next;
		current->next->prev = current->prev;
	}
	delete current;
	_size--;
}

template<typename T>
bool DoublyLinkedList<T>::isEmpty() {
	return _size == 0;
}

template<typename T>
int DoublyLinkedList<T>::size() {
	return _size;
}

template<typename T>
void DoublyLinkedList<T>::printAll() {
	Node<T> *current = head;
	while(current != nullptr) {
		std::cout << current->data << " ";
		current = current->next;
	}
	std::cout << std::endl;
}

Example

int main() {
	DoublyLinkedList<int> list = DoublyLinkedList<int>();
	
	list.insert(1);
	list.insert(2);
	list.insert(3);
	list.insert(4);
	list.insert(5);
	list.printAll();
	std::cout << "size: " << list.size() << std::endl;
	
	list.append(6);
	list.append(7);
	list.append(8);
	list.append(9);
	list.append(10);
	list.printAll();
	std::cout << "size: " << list.size() << std::endl;
	
	list.remove(1);
	list.remove(5);
	list.remove(10);
	list.printAll();
	std::cout << "size: " << list.size() << std::endl;
	
	return 0;
}

/**

5 4 3 2 1 
size: 5
5 4 3 2 1 6 7 8 9 10 
size: 10
4 3 2 6 7 8 9 
size: 7

*/