COMP1850 Lecture 9.1 Linked Lists Flashcards

Flashcards for reviewing linked lists concepts in C and Python.

Linked List

A data structure made up of Nodes containing data and a link (pointer) to the next Node.

Arrays

Stored in a contiguous block in memory, allows direct access via index, and has a fixed size (or can be reallocated).

Linked Lists

Not contiguous in memory, requires traversal for access, and can grow/shrink dynamically.

When to choose a linked list

When you don't know the number of elements, the number of elements change frequently, you'll be adding/removing elements often and accessing an index isn't required.

Head Pointer

A pointer which indicates where the list begins.

Tail

The node at the end of the linked list, which has a NULL pointer.

Traverse

Visiting each node in the list by following the pointers from the Head to NULL.

Creating a New Node

Allocating memory and assigning initial values to create a new node.

Inserting a Node at the Head

Adjusting links from the head and the new node to include the new node at the beginning of the list.

Inserting a Node

Adjusting links to insert a new node into the list at a specific point.

Deleting a Node

Adjusting links to remove a node from the list and freeing the memory.

Deallocating a Node

Releasing allocated memory for the node's data and the node itself.

Linked-list operations

Insertion, Deletion, InsertAtIndex, and Traversal (e.g., search).

Classes in Python

A combination of data attributes that define the object and methods that define object behaviour.

Structs in C

Data attributes that define the object, with functions defined separately and loosely coupled to the data structure.