CHAPTER 10: DATA TYPES AND STRUCTURES

Show understanding that an ADT is a collection of data and a set of operations on those data

Show understanding that a stack, queue and linked list are examples of ADTs.

Describe the key features of a stack, queue and

linked list and justify their use for a given situation

Use a stack, queue and linked list to store data

Describe how a queue, stack and linked list can be implemented using arrays

Singly linked lists

Singly linked lists are a fundamental data structure that consists of a linear chain of nodes. Each node contains two parts:

1. Data: This stores the actual information you want to keep track of, like a number or a name.

2. Next pointer: This pointer references the next node in the sequence, forming the "link" between nodes.

Since singly linked lists only have one pointer per node, you can only traverse the list in one direction, typically from the beginning to the end.

Here are some key points about singly linked lists:

• Dynamic size: Unlike arrays, singly linked lists can grow or shrink on demand. You don't need to pre-define the size.

• Efficient insertions and deletions: Inserting or deleting nodes in the middle of the list can be done in constant time on average.

• Not ideal for random access: Because you can only traverse one way, accessing a specific element by its position (index) might require iterating through the entire list.

Singly linked lists are a versatile data structure with many applications, such as implementing queues, stacks, and even more complex structures like graphs.