Data Structures: Arrays and Linked Lists

Questions and Answers

What is an array?

An array stores a sequence of values.

What is a drawback of arrays?

Capacity of array is fixed

Must know max number of values at compile time

Either runs out of space or wastes space

All of the above (correct)

Static data structures have a fixed size.

True

What do dynamic data structures allow?

They hold an unknown number of elements and can grow or shrink as the program runs. Signup and view all the answers

Which of the following is not a type of dynamic data structure?

Arrays Signup and view all the answers

What does a linked list consist of?

A series of connected nodes. Signup and view all the answers

What is the head of a linked list?

Pointer to the first node. Signup and view all the answers

The last node in a linked list has a successor.

False Signup and view all the answers

What is a node's predecessor?

The previous node in the sequence. Signup and view all the answers

A list's length is the number of ______ in it.

elements/nodes Signup and view all the answers

What does SLL stand for?

Singly-Linked List. Signup and view all the answers

What is the purpose of the 'next' pointer in a node?

To link to the successor node in the list. Signup and view all the answers

What is printed in the traversal method of a linked list?

The elements of the list. Signup and view all the answers

Match the following terms with their definitions:

Node = A unit containing data and a pointer to the next node Head = Pointer to the first node in a linked list Predecessor = The previous node in the sequence Successor = The next node in the sequence Signup and view all the answers

Study Notes

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();
 }
}
```

Description

This quiz covers the fundamental concepts of arrays and linked lists, two essential data structures in programming. It examines the advantages and limitations of static and dynamic data structures, as well as the characteristics of linked lists. Test your understanding of how these structures function and their applications in software development.