Highlights of this lab:

In this lab,  you will:

• Recognize the advantage of Linked Lists.
• Learn the basic operations on Linked Lists.
• Extra Resources

Lab Exercise:

Advantage of Linked Lists.

When you don't know how many elements there will be, and if elements need to be inserted and deleted frequently, it is better to use a linked list. This is because each element for a linked list is created as needed and can be stored anywhere in the free memory space - the elements in the list do not have to be stored in contiguous locations.

Each element in a linked list is referred to as a node. In a simple singly linked list, each element has two fields:

• Data member - contains the data (in our implementation, this is called datum)
• Link member - contains the pointer to the next node (in our implementation, this is called next)

class ListElement
{
  private:    
   int datum;
   ListElement* next;
    
  public:
   ListElement (int, ListElement*);
   
   int getDatum () const;
   ListElement const* getNext () const;
}

A couple of notes on linked lists are:

• if you were implementing a doubly linked list, the above class would have an additional data member to define a pointer to the previous node.
• the last node in any linked list contains a null pointer in the link member.
• the null pointer is used to determine the end of the list.
• notice that there is a constructor in the above implementation that can be used to set the datum and next members.

The following diagram illustrates a simple singly linked list.

In this lab, we use a class to create a linked list. The following is the our LinkedList.h file that contains:

• the definition of the ListElement from above
• the definition of the LinkedList that consists of
  • a head data member that points at the first element of the list
  • some basic linked list operations that we will discuss below

// LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cstdlib>
#include <iostream>
using namespace std;

class LinkedList;  // needed for friend line below

class ListElement
{
  private:    
   int datum;
   ListElement* next;
    
  public:
   ListElement (int, ListElement*);
   
   int getDatum () const;
   ListElement const* getNext () const;

   friend class LinkedList;  // gives LinkedList access to datum and next
};


class LinkedList
{
  private:
   ListElement* head;

  public:
   LinkedList ();
   
   void insertItem (int);
   void makeList ();
   void appendItem (int);
   void deleteItem (int);
   void printList ();
};
#endif

Operations on Linked Lists.

• Creating a List (makeList())

                 First, create a node initialized with a data value and a NULL pointer. 
                 Set the "head" to point to the first node.
                 Set up a current-pointer to the first node (or "head").
                 Get a data value for the next node.
                 While more nodes to add
                 {
                    Create a new node initialized with the data value and a NULL pointer. 
                    Set the current-pointer link member ("next") to the new node.
                    Set the current-pointer to point to the new node.
                    Get a data value for the next node.
                 }
  	

• Adding a Node (appendItem(int item))

                 //Find the end of the list...
                 Set a current-pointer to the "head".
                 While current-pointer link member ("next") is not NULL
                 {
                    Set the current-pointer to the "next" node in the list.
                 }
                 //Now current-pointer points to the last node...
                 Create a new node initialized with the "item" and a NULL pointer. 
                 Set the current-pointer link member ("next") to this new node.
  	  

• Printing Nodes (printList())

                 Set a current-pointer to the "head".
                 While current-pointer is not NULL
                 {
                     Print the data member ("datum") of the current node
                     Set the current-pointer to the "next" node in the list.
                 }
  	

• Inserting Nodes (insertItem(int item))
  This algorithm assumes that you want to insert a node into a list of ordered values. Let's say you have two values, 12 and 24. A new value of 14 should be inserted between these existing values so that the final list will contain the values 12, 14, and 24.

                 Set a previous-pointer to NULL.
                 Set a current-pointer to the "head".
                 //Find where your want to insert into the list...
                 While the new data member > current-pointer value
                 {
                    //Move both pointers along in the list...
                    Set the previous-pointer to the current-pointer
                    Set the current-pointer to the "next" node in the list.
                 }
                 Create a new node initialized with the "item" and current-pointer. 
                 Set the link member in the previous_pointer to the new node.
        

  This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.
  
• Deleting Nodes (deleteItem(int item))

                 If "item" is in the first node
                 {
                     Set a delete-pointer to the first node.
                     Change the "head" pointer to the second node.
                     Delete the node indicated by delete-pointer 
                 }
                 Else
                 {
                     Set a previous-pointer to the "head".
                     While previous-pointer->next is not equal to NULL and 
                           previous-pointer->next->datum is not equal to "item"
                     {
                        Set the previous-pointer to the "next" node in the list.
                     }
                     If you have not reached the end of the list 
                     {
                        Set a delete-pointer to the node to be deleted (Note: it is
                            the node after previous-pointer).
                        Set the link member ("next") of the previous-pointer to the
                            "next" node after delete-pointer.
                        Delete the node indicated by delete-pointer.
                     }
                     Otherwise, print a "not found" message
                 }
  	  

  This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process. If you are reading this, please remember the following bonus word for the Linked List lab exam: tree.

  

Extra Resources

In case you are having trouble understanding Linked Lists, these resources may be helpful:

• https://youtu.be/Zgzoe8jjidk
• https://youtu.be/njTh_OwMljAi (Please note that the concepts are good, but the code is Java and not C++. You might notice that the "*", "->", and "delete" are missing.)
• https://youtu.be/NobHlGUjV3g
• https://www.geeksforgeeks.org/linked-list-set-1-introduction/

---

Lab Exercise: