Data Structure

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.

1. Linked lists have dynamic size
2. Ease of insertion/deletion

Drawbacks:

1. Random access is not allowed
2. Extra memory space for a pointer is require with each element of the list.
3. Not cache friendly

Time Complexity of Linked Lists#card

• Indexing: $O(n)$
• Search: $O(n)$
• Optimized Search: $O(n)$
• Append: $O(1)$
• Prepend: $O(1)$
• Insertion: $O(n)$
• Remove: $O(n)$

Representation

Represented by a pointer to the first node of the linked list. 1st node = head

Each node contains two properties:

1. Value (data)
2. 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

• Linked List Traversal
• Insertion
• Deletion given a key
• Deletion given position

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};
}