Linked List
Similar to arrays, linked list is a linear data structure. However, unlike arrays, linked lists don’t store elements using indices (at low level, these are contiguous memory locations); instead, they store elements using pointers.
Why Linked Lists
Linked Lists are designed to optimize insertion and deletion, slow at indexing and searching.
- Linked lists have dynamic size
- Ease of insertion/deletion
Drawbacks:
- Random access is not allowed
- Extra memory space for a pointer is require with each element of the list.
- Not cache friendly
Time Complexity of Linked Lists#card
- Indexing:
- Search:
- Optimized Search:
- Append:
- Prepend:
- Insertion:
- Remove:
Representation
Represented by a pointer to the first node of the linked list. 1st node = head
Each node contains two properties:
- Value (data)
- Pointer/reference to next node.
A linked list chains nodes together by pointing one node’s reference towards another node.
Types of Linked Lists
There are several types of linked lists.
- Simple Linked list
- Doubly linked list has nodes that also reference the previous node.
- Circularly linked list is simple linked list whose tail, the last node, references the head, the first node.
Used to implement Stacks and Stacks and Queues.
Things I need to master
Link to resources
- https://www.geeksforgeeks.org/linked-list-set-1-introduction/
- https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
- https://www.geeksforgeeks.org/linked-list-set-1-introduction/
- https://github.com/Gongsta/420-LCW-MS-Programming-Techniques-and-Applications/blob/main/lab2/linkedlist_v1.py
Implementation
Taken from CS247.
List.h
file:
#ifndef LIST_H
#define LIST_H
#include <string>
class List {
struct Node;
Node* head;
public:
class Iterator {
Node* cur;
public:
Iterator(Node* cur);
Iterator& operator++();
bool operator!=(const Iterator& other);
std::string& operator*();
};
List();
~List();
void push(const std::string& s);
std::string& ith(int i);
Iterator begin();
Iterator end();
};
#endif
List.cc
file:
#include "List.h"
struct List::Node {
std::string data;
Node* next;
Node(const std::string& data, Node* next): data{data}, next{next} {}
~Node() { delete next; }
};
List::List(): head{nullptr} {}
List::~List() { delete head; }
void List::push(const std::string& s) {
head = new Node{s, head};
}
std::string& List::ith(int i) {
Node* cur = head;
for (int j = 0; j < i; ++j) cur = cur->next;
return cur->data;
}
List::Iterator::Iterator(Node* cur): cur{cur} {}
List::Iterator& List::Iterator::operator++() {
cur = cur->next;
return *this;
}
bool List::Iterator::operator!=(const Iterator& other) {
return cur != other.cur;
}
std::string& List::Iterator::operator*() {
return cur->data;
}
List::Iterator List::begin() {
return Iterator{head};
}
List::Iterator List::end() {
return Iterator{nullptr};
}
Templated version
This is more confusing, less clean, but it has details on how to use the const
iterators.
#ifndef LIST_H
#define LIST_H
#include <string>
class List {
struct Node {
std::string data;
Node* next;
Node(const std::string& data, Node* next): data{data}, next{next} {}
~Node() { delete next; }
};
Node* head;
public:
template<typename DataType> class TemplateIterator {
Node* cur;
explicit TemplateIterator<DataType>(Node* cur): cur{cur} {}
public:
TemplateIterator<DataType>& operator++() {
cur = cur->next;
return *this;
}
bool operator!=(const TemplateIterator<DataType>& other) {
return cur != other.cur;
}
DataType operator*() {
return cur->data;
}
friend List;
};
using Iterator = TemplateIterator<std::string&>;
using ConstIterator = TemplateIterator<const std::string&>;
List();
~List();
void push(const std::string& s);
std::string& ith(int i);
Iterator begin();
Iterator end();
ConstIterator cbegin() const;
ConstIterator cend() const;
};
#endif
#include "List.h"
List::List(): head{nullptr} {}
List::~List() { delete head; }
void List::push(const std::string& s) {
head = new Node{s, head};
}
std::string& List::ith(int i) {
Node* cur = head;
for (int j = 0; j < i; ++j) cur = cur->next;
return cur->data;
}
List::Iterator List::begin() {
return Iterator{head};
}
List::Iterator List::end() {
return Iterator{nullptr};
}
List::ConstIterator List::cbegin() const {
return ConstIterator{head};
}
List::ConstIterator List::cend() const {
return ConstIterator{nullptr};
}