Lists and Linked Lists

List

An Abstract Data Type for storing elements.

Linked List

A data structure consisting of nodes connected by pointers.

Static Data Structure

Size cannot change after creation.

Dynamic Data Structure

Size can grow or shrink during execution.

Abstract Data Type (ADT)

Data type defined by its operations, not implementation.

Queue

An ADT that follows First In First Out principle.

Enqueue

Operation to add an item to the queue.

Dequeue

Operation to remove an item from the queue.

Heap

Memory area for dynamic allocation.

Pointer

Variable that stores the address of another variable.

Built-in List

Predefined list data type in programming languages.

Dynamic List Support

Languages like Python and Java can resize lists.

Memory Location

Specific address in memory for data storage.

Traversal

Process of visiting each element in a list.

Adding Data

Inserting new elements into a list.

Removing Data

Deleting elements from a list.

Operations on Lists

Common functions include add, remove, and traverse.

Real-life List Examples

Students, products, songs, or queue items.

Implementation Hiding

User does not see how data structures work.

Data Types

Basic types like integer, real, and character.

Complex Data Types

Combines basic types for efficient problem-solving.

Dynamic Allocation

Allocating memory at runtime for data structures.

isEmpty()

Checks if the list has no items.

append(item)

Adds item to the end of the list.

remove(item)

Deletes the first occurrence of item.

count(item)

Counts occurrences of item in the list.

len(item)

Returns total number of items in list.

index(item)

Finds the position of item in list.

insert(pos,item)

Inserts item at specified position pos.

pop()

Removes and returns the last item.

pop(pos)

Removes and returns item at position pos.

enqueue

Adds an item to the end of the queue.

dequeue

Removes and returns the front item of the queue.

isFull()

Checks if the queue has reached max size.

isEmpty()

Checks if the queue has no items.

maxSize

Maximum number of items the queue can hold.

circular queue

Queue structure that wraps around when full.

sorting methods

Techniques to arrange list items in order.

merging lists

Combining two or more lists into one.

searching lists

Finding specific items within a list.

comparing lists

Evaluating differences or similarities between lists.

pseudocode

High-level description of algorithm operations.

Random Clothing Task

Worksheet exercise related to list operations.

Linked List

Dynamic data structure using nodes and pointers.

Node

Basic unit of a linked list containing data and pointer.

Data

Information stored in a node, can be complex.

Pointer

Index of the next node in the list.

Start Pointer

Indicates the first node in the linked list.

Nextfree Pointer

Index of the next available space in array.

Array Implementation

Linked list represented using an array structure.

Initialisation

Setting up an empty array as linked list.

Adding Elements

Process of inserting new nodes into the list.

Delete Node

Adjusting pointers to remove a node from the list.

Peeking Ahead

Examining data and pointer of current and next node.

Index

Position of a node within the array.

Null Pointer

Indicates the end of the linked list.

Free Nodes

Nodes that are available for new data insertion.

Head of the List

First node in a linked list.

Adjusting Pointers

Changing pointer references during node operations.

Complex Data Structure

Data type that can hold multiple values.

Dynamic Structure

Size can change during program execution.

List Traversal

Accessing each node in a linked list sequentially.

Linked List Diagram

Visual representation of nodes and pointers.

State of Array

Current configuration of data and pointers in array.

Node Insertion

Process of adding a new node to the list.

Dynamic Data Structure

Data structure that can grow or shrink in size.

Linked List

A collection of nodes where each node points to the next.

Pointer

Reference to the next node in a linked list.

Inserting a Node

Adding a new node to a linked list.

Deleting a Node

Removing a node from a linked list.

Static Data Structure

Fixed size data structure, cannot change size.

Array of Records

Data structure storing multiple records in contiguous memory.

nextfree

Pointer to the next available space in the list.

List[p].Pointer

Pointer indicating the next node in the list.

List[next].data

Data stored in the node pointed by next.

List[next].pointer

Pointer in the next node, indicating its successor.

Queues

Abstract data type that follows FIFO principle.

Stacks

Abstract data type that follows LIFO principle.

Trees

Hierarchical data structure with nodes and edges.

Algorithm

Step-by-step procedure for solving a problem.

Processing a Linked List

Performing operations like traversal, insertion, deletion.

Task 3

Worksheet task focused on linked list algorithms.

Copyright

Legal protection of original works and materials.

Licence Agreement

Contract defining usage rights of materials.

Plenary

Session summarizing key points of a topic.