DTL

List

Go back

Introduction

Lists are sequence containers that allow non-contiguous memory allocation using nodes. As compared to vector, the list has slow traversal, but once a position has been found, insertion and deletion are quick.

Advantages

  • Overflow can never occur unless the memory is actually full.
  • Compared to vector, insertions and deletions are quick.
  • With large records, moving pointers is easier and faster than moving the items themselves.

Disadvantages

  • The pointers require extra space.
  • Do not allow random access.
  • Slow traversal.

Types

There are four key types of linked lists:

  • Singly Linked Lists
  • Doubly Linked Lists
  • Circular Linked Lists
  • Circular Doubly Linked Lists

Using list with DTL

Different ways to initialize a list

  1. Initializing an empty list:
    2. #include "list.hpp"
#include <iostream>

int main() {
  // Static
  dby::List<int> myStaList;

  // Pointer
  dby::List<int>* myPtrList = new dby::List<int>();
  delete myPtrList;

  return 0;
}
  2. Initializing like arrays:
    3. #include "list.hpp"
#include <iostream>

int main() {
  // Static
  dby::List<int> myStaListOne = { 1, 2, 3, 4, 5 };
  dby::List<int> myStaListTwo { 1, 2, 3, 4, 5 };
  // myStaListOne = 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
  // myStaListTwo = 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

  // Pointer
  dby::List<int>* myPtrList = new dby::List<int>({ 1, 2, 3, 4, 5 });
  // myPtrList = 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

  delete myPtrList;
  return 0;
}

Accessing stored data in the list

  1. Using at():
    2. #include "list.hpp"
#include <iostream>

int main() {
  // Static
  dby::List<int> myStaList = { 21, 84, 96, 73, 50 };
  std::cout << "Element at pos 1: " << myStaList.at(1) << '\n'; // 84

  // Pointer
  dby::List<int>* myPtrList = new dby::List<int>({ 21, 84, 96, 73, 50 });
  std::cout << "Element at pos 2: " << myPtrList->at(2); // 96

  delete myPtrList;
  return 0;
}

Iterating over a list

  1. For each loop:
    2. #include "list.hpp"
#include <iostream>

int main() {
  // Static
  dby::List<int> myStaList = { 1, 2, 3, 4, 5 };
  myStaList.for_each([](int val){ std::cout << val << ' '; });

  // Pointer
  dby::List<int>* myPtrList = new dby::List<int>({ 1, 2, 3, 4, 5 });
  myPtrList->for_each([](int val){ std::cout << val << ' '; });

  delete myPtrList;
  return 0;
}

Other list methods

  • size(): Returns the number of elements in the list.
  • empty(): Returns whether the list is empty or not.
  • front(): Returns a reference to the first element in the list.
  • back(): Returns a reference to the last element in the list.
  • middle(): Returns a reference to the middle element in the list.
  • insert(std::size_t index, T data): Insert a new element at a specified position.
  • push_front(T value): Adds a new element at the beginning of the list.
  • push_back(T value): Adds a new element at the end of the list.
  • erase(std::size_t index): Remove an element from the list at the specified position.
  • pop_front(): Removes the first element of the list.
  • pop_back(): Removes the last element of the list.
  • resize(std::size_t new_size): Resizes the list so that it contains 'new_size' elements.
  • reverse(): Reverses the order of the elements in the list.
  • sort(bool(*compare)(T a, T b)): Sorts the list using a compare function (incresing order by default).
  • clear(): Remove all the elements of the list.
  • filter(bool(*condition)(T value), void(*doThis)(T value)): If the 'condition' function is true it applies the 'doThis' function.
  • search(T value, bool(*compare)(T first_val, T second_val)): Find if a value is stored in the list by making a comparison. 'Compare' is an optional parameter to modify the compare behavior between two elements.
  • search_if(bool(*condition)(T value)): Find if any element of the list satisfies a 'condition' function.
  • find(T data, bool(*comparison)(T a, T b)): Returns a pointer to the data if it is stored in the list.
  • count_if(bool(*condition)(T value)): Returns the number of elements in the list for which the 'condition' function returns true