Data Structure and Algorithm Design

Chapter 7

Xingang (Ian) Fang

Sections

  • List ADT and implementations

  • Linked-list

List Abstract Data Type

Try list operations in our ADT Explorer.

  • Overview

  • Behaviors

Overview

  • A list ADT is a sequential collection of elements.

  • It models a finite ordered sequence of elements.

  • Characteristics

    • Sequential - the elements are ordered in a sequence

    • Finite - there is a first and last element

    • Indexable - each element has a unique positional index to allow random access

    • Dynamic - the size of the list can change

    Note

    There are other definitions for list ADT. It can be heterogeneous, non-indexable, etc. We stick to the most common definition.

  • Concepts

    • Index - a unique integer that identifies an element in the list by its position

    • Value - the value stored as an element in the list

Behaviors

  • Access by index

  • Insertion by index/value

  • Deletion by index/value

  • Search a value

  • Traversal (visit/print all in an order)

  • Get size (check empty)

  • Clear

C++ Implementation of a List ADT

  1. Existing C++ STL containers

  2. Make from scratch as templates

    • Partially filled array

    • Linked list

    ** Node struct**

    template <typename T>
struct Node {
  T data;
  Node<T> *prev;
  Node<T> *next;
};

Linked List Example

template <typename T>
class List {  // Doubly-linked list
  Node<T> *head;
  Node<T> *tail;
  int size;
public:
  List();
  ~List();
  void clear();
  void append(const T &data);
  void insertBefore(const T &data, Node<T> *next);
  void remove(Node<T> *node);
  Node<T> *search(const T &data);
  int getSize() const;
};

Choice of Data Structures

  • No data structure is perfect

  • Linked List

    • fast insertion and removal

    • slow indexing

  • Array

    • fast indexing

    • fixed size

    • slow insertion and removal

  • Advanced data structures (FYI)

    • In the cost of complex logics or extra spaces

    • hybrid: linked list with array indices

    • skip list

    • hash table

    • search tree

Linked-List in C++

Xingang (Ian) Fang

Overview

  • A linked data structure

  • Models a sequential collection of elements

  • Linked nodes (class/struct) are connected by links (C++ pointers)

  • Logically contiguous, but not physically contiguous

  • Advantages

    • Dynamic size

    • Efficient insertion and removal

    • Not requiring contiguous memory

    • Sequential access

  • Limitations

    • Inefficient random access

    • Extra memory space for links

digraph ll { rankdir=LR; node [shape=record]; head [label="head"]; a [label="{ <data> 12 | <ref> }", width=1.2]; b [label="{ <data> 99 | <ref> }"]; c [label="{ <data> 37 | <ref> }"]; head:e -> a:data [arrowhead=vee, arrowtail=none, dir=both, tailclip=false]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; }

A minimal linked-list

Linked-List Variations

  • Minimal implementation: a head pointer; singly-linked

  • Ideal implementation: a head pointer, a tail pointer, and a size; doubly-linked

  • Instance variables

    • head pointer

    • tail pointer (optional)

    • size (optional)

  • Number of links per node

    • singly-linked - a pointer to next node

    • doubly-linked - pointers to previous and next nodes

  • Other variations (FYI)

    • Circular linked list

    • Dummy node before the first node

Operations and Time Complexity

  • Based on the ideal implementation

  • Access

    • by index \(\Theta(n)\)

    • first \(\Theta(1)\)

    • last \(\Theta(1)\)

  • Insertion/removal

    • at the beginning \(\Theta(1)\)

    • at the end \(\Theta(1)\)

    • at a specified position (by pointer/iterator) \(\Theta(1)\)

    • at a specified position (by index) \(\Theta(n)\)

C++ Implementation Details

  • Linked list class

    • head pointer

    • tail pointer (optional)

    • size (optional)

  • Linked node class/struct

    • top-level or nested

  • Use class templates for generalization

    • type of data stored in nodes can be parameterized

Visualization