Dynamic Data Structures (Pt.2)

C. Papachristos

Robotic Workers Lab

University of Nevada, Reno

CS-202

Course , Projects , Labs:

​

​

​

​

Your 8^th Project will be announced today Thursday 4/9.

Smart Pointer(s) extra-grade Project X was extended to Thursday 4/9 as well !

• NO Project accepted past the 24-hrs delayed extension (@ 20% grade penalty).
• Send what you have in time!

​

Course Week

CS-202 C. Papachristos

Today’s Topics

CS-202 C. Papachristos

Dynamic Data Structures

​

Node – Based Containers

Forward –or– Singly Linked List(s)

Doubly – Linked List(s)

​

Array – Based Containers

​

(Singly – Linked) Node(s)

CS-202 C. Papachristos

The Forward Node(s) (of the FL)

​

A Singly-Linked Node of the FL is an element of the Dynamic Data Structure.

​

• Typically a class encapsulating Data Object(s).
• Holds Data & Pointer to associate “Next” Node�in the Forward–Linked List.
• List implementation has to Access & Mutate it.

​

m_next

0x…

Node k

class Node {

public:

// ctor(s)

// dtor (?)

// get - set methods

​

…

friend class ForwardList;

…

​

private:

DataType m_data;

Node * m_next;

};

Provide Get/Set methods or give class List direct access to class Node members.

Necessary: Maintains association(s) to other �FL Nodes.

Can:

• Point to�another Node.
• Be a “NULL Pointer” (nullptr/NULL).

Stored Data can be simple data types (int, double, …) or complex ones (classes/ structs).

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

The Forward-List

​

The Structure:

​

• Each Node contains Data and the Address of “Next” Node in the Forward-List.
• Forward-List has a Head pointer to “First” Node.

m_next

0x…

Node k+1

m_next

0x…

Node k

m_head

m_next

0x…

Node k+n

m_next

0x…

Node …

NULL

for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next)

​

cout << curr->m_data << endl; //(overloaded) insertion for m_data type

CS-202 C. Papachristos

Forward-List Traversal

​

To perform FL Traversal, a control loop is used:

​

m_head

curr

m_next

0x…

Node 1

m_next

0x…

Node 0

m_next

0x…

Node …

NULL

m_next

0x…

Node n

Forward List (Singly-Linked Node-based)

for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next)

​

cout << curr->m_data << endl; //(overloaded) insertion for m_data type

CS-202 C. Papachristos

Forward-List Traversal

​

To perform FL Traversal, a control loop is used:

​

m_head

curr

m_next

0x…

Node 1

m_next

0x…

Node 0

m_next

0x…

Node …

NULL

m_next

0x…

Node n

Forward List (Singly-Linked Node-based)

for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next)

​

cout << curr->m_data << endl; //(overloaded) insertion for m_data type

CS-202 C. Papachristos

Forward-List Traversal

​

To perform FL Traversal, a control loop is used:

​

m_head

curr

m_next

0x…

Node 1

m_next

0x…

Node 0

m_next

0x…

Node …

NULL

m_next

0x…

Node n

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Insertion

​

Find target Node to insert after.

​

m_head

curr

m_next

0x…

Node …

m_next

0x…

Node 0

m_next

0x…

NULL

m_next

0x…

Node n

Node k

for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next)

if ( curr->m_data == … ){

Node * newNode_pt = new Node(data, curr->m_next);

curr->m_next = newNode_pt;

}

}

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Insertion

​

Create new Node to insert & ensure Forward–Connection.

​

m_head

curr

m_next

0x…

Node …

m_next

0x…

Node 0

m_next

0x…

NULL

m_next

0x…

Node n

Node k

for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next)

if ( curr->m_data == … ){

Node * newNode_pt = new Node(data, curr->m_next);

curr->m_next = newNode_pt;

}

}

m_next

0x…

newNode

newNode_pt

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Insertion

​

Inter-connect inserted Node into the FL.

​

m_head

curr

m_next

0x…

Node …

m_next

0x…

Node 0

m_next

0x…

NULL

m_next

0x…

Node n

Node k

for (Node * curr = m_head; curr!=nullptr; curr = curr->m_next)

if ( curr->m_data == … ){

Node * newNode_pt = new Node(data, curr->m_next);

curr->m_next = newNode_pt;

}

}

m_next

0x…

newNode

newNode_pt

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Node Erasing

​

Find the predecessor of the target Node to delete.

​

for (Node * curr = m_head; curr!=NULL; curr = curr->m_next)

Node * delNode_pt = curr->m_next;

if ( delNode_pt!=nullptr && delNode_pt->m_data == … ){

curr->m_next = delNode_pt->m_next;

delete delNode_pt;

}

m_head

m_next

0x…

Node …

m_next

0x…

m_next

0x…

NULL

m_next

0x…

Node n

Node k

Node 0

curr

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Node Erasing

​

Memorize the Node that is the candidate to be deleted.

​

for (Node * curr = m_head; curr!=NULL; curr = curr->m_next)

Node * delNode_pt = curr->m_next;

if ( delNode_pt!=nullptr && delNode_pt->m_data == … ){

curr->m_next = delNode_pt->m_next;

delete delNode_pt;

}

m_head

m_next

0x…

Node …

m_next

0x…

m_next

0x…

NULL

m_next

0x…

Node n

Node k

Node 0

delNode_pt

curr

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Node Erasing

​

Change the Link of predecessor Node.

​

for (Node * curr = m_head; curr!=NULL; curr = curr->m_next)

Node * delNode_pt = curr->m_next;

if ( delNode_pt!=nullptr && delNode_pt->m_data == … ){

curr->m_next = delNode_pt->m_next;

delete delNode_pt;

}

m_head

m_next

0x…

Node …

m_next

0x…

m_next

0x…

NULL

m_next

0x…

Node n

Node k

Node 0

curr

delNode_pt

Forward List (Singly-Linked Node-based)

CS-202 C. Papachristos

Forward-List Node Erasing

​

Deallocate dynamic memory of target Node.

​

for (Node * curr = m_head; curr!=NULL; curr = curr->m_next)

Node * delNode_pt = curr->m_next;

if ( delNode_pt!=nullptr && delNode_pt->m_data == … ){

curr->m_next = delNode_pt->m_next;

delete delNode_pt;

}

m_head

m_next

0x…

Node …

m_next

0x…

m_next

0x…

NULL

m_next

0x…

Node n

Node k

Node 0

curr

delNode_pt

Forward List (Singly-Linked Node-based)

(Doubly – Linked) Node(s)

CS-202 C. Papachristos

The Node(s) (of the List)

​

A Node of the List is an element of the Dynamic Data Structure.

​

• Typically a class encapsulating Data Object(s).
• Holds Data & Pointer to associate “Next” Node�as well as “Previous” Node in the Doubly–Linked List.
• List implementation has to Access & Mutate it.

​

m_next

0x…

Node k

class Node {

public:

// ctor(s)

// dtor (?)

// get - set methods

​

…

friend class List;

…

​

private:

DataType m_data;

Node * m_next;

Node * m_prev;

};

Provide Get/Set methods or give class List direct access to class Node members.

Necessary: Maintain association(s) to other �List Nodes.

Can:

• Point to�another Node.
• Be nullptr.

Stored Data can be simple data types (int, double, …) or complex ones (classes/ structs).

m_prev

Doubly – Linked List(s) (Node-based)

CS-202 C. Papachristos

The Doubly Linked-List

​

An example Doubly Linked-List:

​

• Each Node additionally contains Address of “Previous” Node in the Linked-List.
• Linked-List has a Head & a Tail pointer to respective “First” & “Last” Node.

m_next

0x…

Node k+1

m_next

0x…

Node k

m_head

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

NULL

Doubly – Linked List(s) (Node-based)

CS-202 C. Papachristos

• Forward –or– Singly Linked List
• We can traverse it by following links in only one direction!
• Doubly – Linked List
• 2 Links: One link to the next node and one link to the previous node.
• This means we can follow links in either direction!
• A Node with a Next nullptr signifies the end of the list.
• A Node with a Previous nullptr signifies the beginning of the list.
• Can make some operations easier, e.g. erasing elements, since we don’t need to search the list to find the node before the one we want to remove

(Doubly – Linked) Node Class

CS-202 C. Papachristos

class Node{

​

friend class List;

public:

​

Node()

: m_next(nullptr), m_prev(nullptr) { }

​

Node(const DataType & data, Node * next = nullptr, Node * prev = nullptr)

: m_next(next), m_prev(prev), m_data(data) { }

Node(const Node & other)

: m_next(other.m_next), m_prev(other.m_prev), m_data(other.m_data) { }

​

DataType & data(){ return m_data; } //by-Reference access to data (allows mutation/writing)

const DataType & data() const{ return m_data; } //by-const-Reference access to data (read-only)

private:

Node * m_next;

Node * m_prev;

DataType m_data;

};

//allows direct accessing of links m_next & m_prev

// from list class (otherwise, link remains

// inaccessible outside of Node)

m_next

m_prev

0x…

Node k

Inserting in the Front of Doubly – Linked List

CS-202 C. Papachristos

Existing List before adding new Node :

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

Inserting in the Front of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_next

0x…

Node k

m_prev

NULL

m_head

NULL

newHead_pt

newHead_pt new Node created by:

​

Node * newHead_pt = new Node(DataType(…), m_head, nullptr);

Inserting in the Front of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_next

0x…

Node k

m_prev

NULL

m_head

newHead_pt new Node created by:

​

Node * newHead_pt = new Node(DataType(…), m_head, nullptr);

NULL

newHead_pt

const DataType & data

Node * next

Node * prev

Inserting in the Front of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_next

0x…

Node k

m_prev

NULL

m_head

Set the previous link of the original m_head Node:

​

m_head->m_prev = newHead_pt;

newHead_pt

Inserting in the Front of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_next

0x…

Node k

m_prev

NULL

Set the List head to newHead.

​

m_head = newHead_pt;

newHead_pt

m_head

Inserting in the Middle of Doubly – Linked List

CS-202 C. Papachristos

Existing List before adding new Node :

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

After some�curr Node:

curr

Inserting in the Middle of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

After some�curr Node:

m_next

0x…

Node k

m_prev

Create and “wire” new Node in:

Node * newNode_pt =

new Node(DataType(…),

curr->m_next,

curr);

newNode_pt

curr

Inserting in the Middle of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

After some�curr Node:

m_next

0x…

Node k

m_prev

newHead_pt

curr

“Wire” existing Nodes to it:

curr->m_next = newNode_pt;

if (newNode_pt->m_next)

newNode_pt->m_next->m_prev =

newNode_pt

​

Inserting in the Middle of Doubly – Linked List

CS-202 C. Papachristos

Existing List before adding new Node :

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

Before some�curr Node:

curr

Inserting in the Middle of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

Before some�curr Node:

m_next

0x…

Node k

m_prev

Create and “wire” new Node in:

Node * newNode_pt =

new Node(DataType(…),

curr,

curr->m_prev);

newNode_pt

curr

Inserting in the Middle of Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

Before some�curr Node:

“Wire” existing Nodes to it:

curr->m_prev = newNode_pt;

if (newNode_pt->m_prev)

newNode_pt->m_prev->m_next =

newNode_pt

​

m_next

0x…

Node k

m_prev

newNode_pt

curr

Erasing a Node from a Doubly – Linked List

CS-202 C. Papachristos

Less complicated algorithm:

• In the Forward list, we had to hold a reference to the Predecessor Node of the one we wished to erase. The only way to do that is via Traversal and 1 step look-ahead…
• Thanks to the additional backward link m_prev we do not need this auxiliary variable, or to perform Traversal.
• In the Doubly – Linked List we can access a prior node via curr_node->m_prev .

A bit more work when updating associations:

• Removing a node requires updating m_next & m_prev (the references on both sides of the node we wish to erase).

Erasing a Node from a Doubly – Linked List

CS-202 C. Papachristos

Existing list before removing delNode_pt :

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

delNode_pt

Erasing a Node from a Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

Get pointers to the previous and next Nodes:

​

Node * delNode_prev = delNode_pt->m_prev;

Node * delNode_next = delNode_pt->m_next;

delNode_pt

delNode_prev

delNode_next

Removing a Node from a Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

delNode_pt

Bypass delNode_pt (step 1):

​

delNode_prev->m_next = delNode_next;

delNode_prev

delNode_next

Erasing a Node from a Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

delNode_pt

Bypass delNode_pt (step 2):

​

delNode_prev->m_next = delNode_next;

delNode_next->m_prev = delNode_prev;

delNode_prev

delNode_next

Erasing a Node from a Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k+1

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_prev

m_head

NULL

delNode_pt

Delete delNode_pt :

​

delete delNode_pt;

delNode_prev

delNode_next

Erasing a Node from a Doubly – Linked List

CS-202 C. Papachristos

m_next

0x…

Node k

m_next

0x…

Node k+n

m_next

0x…

Node …

m_tail

NULL

m_prev

m_prev

m_prev

m_head

NULL

Existing list after removing delNode_pt :

Array – based Containers

CS-202 C. Papachristos

The Elements(s) (of the AC)

​

An Item of the AC is an element of the Dynamic Data Structure.

​

• Typically Data Object(s).
• Contiguously stored within an array.
• Data Organization implicitly determined by Array order.

​

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC […]

0x…

AC [s]

0x…

AC […]

0x…

AC [m]

Next AC element lies at index +1 , previous at index -1.

Simple Pointer arithmetic (++ / --) traverses through the AC.

Array – based Containers

CS-202 C. Papachristos

The Structure (of the AC)

​

The AC can be variably filled. Use variables to track:

​

• The data array total size: m_capacity.
• The data array currently filled size: m_size.

​

m_size < m_capacity : Partially filled AC.

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC […]

0x…

AC [s]

0x…

AC […]

0x…

AC [c]

Array – based Containers

CS-202 C. Papachristos

The Structure (of the AC)

​

​

​

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC […]

0x…

AC […]

m_size = m_capacity : Completely filled AC.

0x…

AC […]

0x…

AC [s]

m_size = 0 : Completely empty AC.

0x…

AC [c]

0x…

AC […]

0x…

AC […]

0x…

AC […]

0x…

AC […]

0x…

AC […]

0x…

AC […]

s = c

s = 0

Array – based Containers

CS-202 C. Papachristos

Insertion (into the AC)

​

Need to “Shuffle” – upwards.

​

• If partially filled and new data “fits”, no re-allocation.
• Otherwise, allocate new data array, copy contents, delete old data array.

​

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC […]

0x…

AC […]

0x…

AC [s]

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC [j]

0x…

AC […]

0x…

AC […]

0x…

AC [s]

0x…

AC [c]

Array – based Containers

CS-202 C. Papachristos

Erasing (from the AC)

​

Need to “Shuffle” – downwards.

​

• Copy over data from right to left, overwriting array elements.
• Update necessary auxiliary variables – such as: m_size, m_capacity

​

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC [j]

0x…

AC […]

0x…

AC […]

0x…

AC [s]

0x…

AC [0]

0x…

AC […]

0x…

AC [i]

0x…

AC […]

0x…

AC […]

0x…

AC [s]

0x…

AC [c]

Time for Questions !

CS-202

CS-202 C. Papachristos