C++ Linked Lists   «Prev  Next»
Lesson 4A singly linked list
ObjectiveExamine an implementation of a self-referential dynamic data structure.

Examine C++ Singly Linked List

Here's a breakdown of the purpose and function of a Singly Linked List in C++:
  • Dynamic Data Structure: Singly Linked Lists provide a way to store a collection of data where the number of elements can grow or shrink as needed, unlike arrays which have a fixed size.
  • Efficient Insertion and Deletion (At Specific Points): They are optimized for scenarios where you frequently need to add or remove items at the beginning or within the list, providing better performance for those operations compared to arrays.
  • Memory Management: Linked lists can use memory in a more flexible way, preventing issues like fragmentation.

Function: A Singly Linked List is built with these core components:
  • Nodes: Each node contains two elements:
    • The data itself (which could be a number, string, or a more complex data structure).
    • A pointer (reference) to the next node in the list.
  • Head: A pointer that references the first node in the list.
  • Tail: A pointer referencing the last node in the list. Often, this tail node will contain a null pointer to signify the end of the list.

Key Operations
  • Insertion:
    • At the beginning: A new node is created, its `next` pointer is set to the current head, and then the new node becomes the head.
    • Anywhere else: You traverse the list until you find the desired position, and then adjust the pointers of surrounding nodes to include the new node.
  • Deletion:
    • At the beginning: The `head` pointer is updated to point to the second node.
    • Anywhere else: Traverse the list to find the node before the one to be deleted, and adjust its `next` pointer to skip the node being removed.
  • Traversal: Starting at the `head`, you follow the `next` pointers of each node to access the data in sequence.

Use Cases
  • Implementing stacks and queues.
  • Representing graphs in Graph Theory.
  • Applications where you need to frequently insert or delete elements in places other than the end of the sequence.

Self-referential Dynamic Data Structure

A singly linked list data type is a prototype for many useful dynamic data structures called self-referential structures. These data types have pointer members that refer to objects of their own type.
The following class declaration implements a singly linked list:
//A singly linked list

struct slistelem {
   char       data;  // could be replaced by a
                     // complicated type capable of
                     // storing a range of information
   slistelem*  next; // points to the next slistelem
                     // in the list

class slist {
   slist() : h(0) { }       //0 is empty slist
   ~slist() { release(); }
   void  prepend(char c);   //adds to front slist
   void  del();
   slistelem*  first() const { return h; }
   void  print() const;
   void  release();
   slistelem* h;            //head of slist

Diagram of singly-linked list
Diagram of singly-linked list

Constructor initializes the head of the List

The constructor initializes the head of slist pointer h to the value 0, which is called the null pointer constant, and it can be assigned to any pointer type. In linked lists, it typically denotes the empty list or end-of-list value.
The class slist has functions that perform the following operations:

  1. prepend - Add to front of list
  2. first - Return first element
  3. print - Print list contents
  4. del - Delete first element
  5. release - Destroy list

Over the next several lessons, we'll examine each of these functions more closely.

SEMrush Software