🪴 Avril Chen

Search

SearchSearch

Linked List

Similar to arrays, linked list is a linear data structure. Unlike arrays, linked lists don’t store elements using indices, instead, they store elements using pointers.

Linked Lists are very good for insertion and deletion, but slow at indexing and searching.

Usually represented by a pointer to the first node called head of the linked list. Each node contains two properties:

  1. Value (data)
  2. Pointer/reference to the next node in the list

A linked list chains nodes together by pointing to the next node.

Types of linked lists:

  • Simple Linked Lists
  • Doubly linked list has nodes that also reference the previous node
  • Circularly linked lists is simple linked list whose tail is the last node’s reference and a head which points at the first node.

Used to implement Stack and Queue.

Implementation

From CS247 - Software Engineering Principles.

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

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

Graph View

Backlinks