Data Structures: Arrays and Linked Lists

Review of Arrays

• An array stores a fixed sequence of values defined by the syntax: arrayType arrayName[ numberOfElements ].
• Drawbacks include:
  • Fixed capacity; cannot change size dynamically.
  • Maximum number of values must be known at compile time.
  • Potential to run out of space or waste allocated space.
  • Arrays can only hold data of the same data type.
• Static data structures have a predetermined size.

Dynamic Data Structures

• These structures can hold an unknown number of elements, allowing capacity to grow or shrink during execution.
• Generic type data structures can hold elements of different data types.
• Common types include:
  • Linked Lists
  • Stacks
  • Queues
  • Trees

Linked Lists

• Composed of a series of connected nodes.
• Each node contains:
  • A piece of data (which can be of any type).
  • A pointer to the next node in the list.
• The head of the list points to the first node, while the last node points to NULL.

Node Terminology

• Successor: The next node in the sequence (last node has no successor).
• Predecessor: The previous node in the sequence (first node has no predecessor).
• List Length: Total number of nodes in the list; can be empty.

Singly-Linked Lists (SLL)

• In a singly-linked list, each node has a value and a pointer to its successor.
• The head points to the first node or contains a null link if the list is empty.

Example of a Node Class in C++

• Node includes private attributes:
  • int value;
  • Node* next;
• Constructor initializes next as NULL.
• Public methods include getters and setters for value and next node.

Creating a Singly-Linked List

• Example of initializing nodes:
  • Node* temp = new Node(17, NULL);
  • Links nodes sequentially:
    • temp = new Node(23, temp);
    • temp = new Node(97, temp);
  • Finally, create the list with head node:
    • Node* myList = new Node(44, temp);

Traversing a Singly-Linked List

• A method to traverse and print elements of the list involves:
  • Starting from the head node and using a pointer to traverse until NULL is reached.
  • Example method structure:

    void print() {
        Node *here = this;
        while (here != NULL) {
            cout << here->getValue() << " ";
            here = here->getNext();
        }
    }