Shallow copy and Deep copy

​Introduction

• In the most generic sense, a list is simply a finite sequence of elements

  – More appropriately, it is a storage structure for a finite sequence of elements

• An array is one example of a list

• BUT

  – Arrays tend to be inflexible

  – Usually need to know the maximum size that is ever needed

  • But that’s hard to guarantee

  • Can easily waste storage if not fully utilized

Node

• This is where we are going to really put pointers and dynamic memory to work

• Pointer variables are usually part of a structure called a node

• The node has two parts:

  • Information, or data, and

  • A pointer to another node

NODE

Linked Lists

• Another way to organize data items

  – Place them within objects—usually called nodes

  – Linked together into a “chain,” one after the other

Kind of like a freight train

A node, with a string as the data item

Several nodes linked together to form a linked list

• There is also a special pointer, called the head pointer.

• It points to the first node in the list

A head pointer to the first of several linked nodes

• Linked lists can grow and shrink as needed, unlike arrays, which have a fixed size

Linked lists can insert a node between other nodes easily

Empty List

• If a list currently contains 0 nodes, the list still exists

• It is the empty list

• In this case the head pointer is the nullptr

Pointer-Based Linked Lists

A node in a linked list is sometimes defined as a template struct

A "Node" struct

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

//A node is dynamically allocated
Node<T> *p;
p = new Node<T>;

#ifndef NODE_H
#define NODE_H
template <typename T>
struct Node
{
    T data; // Node value
    Node<T> *next; // Pointer to the next node
    
    Node (T nodeValue) // Constructor
    { data = nodeValue;
    next = nullptr;}
};
#endif

Defining a Linked List

• Define a pointer for the head of the list:

  • Node *head = nullptr;

• Head pointer initialized to nullptr to indicate an empty list

NULL pointer

• Is used to indicate end-of-list

• Should always be tested for before using a pointer:

  • Node *p;

  • while (p != nullptr) ...

• Can also test the pointer itself:

  • while (!p) ... // same meaning as above

Operations

• Basic operations:

  • append a node to the end of the list

  • insert a node within the list

  • traverse the linked list

  • delete a node

  • delete/destroy the list

Create a New Node

• Allocate memory for the new node:

  • Node* newNode = new Node;

• Initialize the contents of the node:

  • newNode->data = num;

• Set the pointer field to the null pointer:

  • newNode->next = nullptr;

Appending a Node

• Add a node to the end of the list

• Basic process:

  • Create the new node (as already described)

  • Add node to the end of the list:

    • If list is empty, set head pointer to this node

    • Else,

      • traverse the list to the end

      • set pointer of last node to point to new node