Data structures include:

• stacks
• queues
• ordered linked list

Linked List

Issues with Arrays

The issue with arrays is that if you want to add another element, you have to create a new array with size + 1 and copy over the old array elements. Arrays are not flexible enough for an efficient implementation of data structures.

int arr = [1, 2, 3, 4];
int* arr = new int[4];

“Flexibility” means we need to have the ability to extend or shrink our data structure.

Enter the Linked List

• We have an object called “Node”, which is the basic element of a linked list.
• Every node has data members and a pointer to the next node.
• We have a pointer (of type pointer-to-Node) called “Head” that stores the address of the first node so we can refer to the linked list and do stuff with it.

Implementation in C

The implementation of these data structures in C could be done using the struct keyword.

Implementation in C++

We can use the class keyword because we can combine data members and function members.

Node Class

base class for data structures