Linked List

Single Linked List

Characteristics

• Consists of nodes
  • data
  • pointer to next node
• Stores similar elements
• Elements are linked in memory but stored non-contiguously
• Does not allow random access

Operations

• Adding
  • PushFront(Key) - O(1)
  • PushBack(Key) - O(n)
  • AddBefore(Node, Key) - O(n)
  • AddAfter(Node, Key) - O(1)
• Removal
  • PopFront() - O(1)
  • PopBack() - O(n)
  • Erase(Key) - O(n)
  • Empty() - O(1)
• Access
  • TopFront() - O(1)
  • TopBack() - O(n)
  • Find(Key) - O(n)

Pros/Cons

• Pros
  • Adding/Removing in front is faster, O(1)
• Cons
  • Expensive for random access, O(n)
  • TopBack, PushBack, PopBack, and AddBefore are expensive because the list only links forwards and there is no tail pointer
• Note: Cannot use binary search on linked lists because there is not a concept of indices

Implementation

struct Node {
	int data;
	Node *next;
};
 
struct List {
	int size;
	Node* head;
 
	List()
	void push_front(int);
}
 
 
List::List() {
	size = 0;
	head = new Node;
    tail = new Node;
	head -> next = tail;
}
 
void List::push_front(int x) {
	Node* temp = new Node;
	temp->data = x;
	temp->next = head->next;
	head->next = temp;
	size++;
}

Single Linked List with Tail

Performance

• PushBack - O(1)
• TopBack - O(1)
• Others same as Single No Tail

Pros/Cons

• Pros
  • Solves the issue of PushBack and TopBack
• Cons
  • Extra Memory
  • Still bad random access

Doubly Linked List with Tail

Performance Changes

• PushBack - O(1)
• PopBack - O(1)
• TopBack - O(1)
• AddBefore - O(1)
• Others same as Single No Tail

Pros/Cons

• Pros
  • Solves the issue of PopBack and AddBefore from singly
• Cons
  • Extra Memory
  • Still bad random access