IB COMPUTER SCIENCE | Linked Lists for Topic 5

ABSTRACT DATA STRUCTURES | LINKED LISTS

Topics from the IB Computer Science Specification 2014

ALSO IN THIS TOPIC
RECURSION
DATA STRUCTURES
YOU ARE HERE | LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS

SECTION 1 | DYNAMIC DATA STRUCTURES

A dynamic data structure is a data structure that can grow or shrink in size during the execution of a program, as opposed to a static data structure with a fixed size. This adaptability allows dynamic data structures to efficiently manage memory and handle varying data requirements. Some common examples of dynamic data structures are linked lists, trees, and graphs. Key features and characteristics of dynamic data structures include nodes, pointers, and dynamic memory allocation.

Nodes: A node is a fundamental unit of a dynamic data structure, representing an individual element within the structure. Each node typically contains two components: data and a reference (or multiple references) to other nodes. The data component stores the actual value or information, while the reference(s) establish connections between nodes to define the structure's overall organization.
Pointers: Pointers are variables that store the memory addresses of other variables or objects. In dynamic data structures, pointers are used to reference or "point to" other nodes within the structure, thereby creating links between them. By updating the pointers, the structure can be modified, such as by adding or deleting nodes, without affecting the actual data.
Dynamic Memory Allocation: Dynamic data structures rely on dynamic memory allocation, which allows memory to be allocated or deallocated during the program's execution. This capability enables dynamic data structures to efficiently manage memory by only allocating space when needed and releasing it when no longer in use.

Dynamic data structures are particularly useful when dealing with varying or unpredictable data sizes, as they can easily expand or contract as needed. However, they may require more complex algorithms and management compared to static data structures, which could result in higher overhead and slower performance in certain situations.

SECTION 2 | WHAT ARE LINKED LISTS

Linked lists are a dynamic data structure that link each element (node) in the list to the next via a pointer / address of the next element, by doing this items/elements within the list do not need to be stored consecutively.

myList = ["Dave", "Jill", "Jane", "Bill", "Betty"]

Imagine the list above has been stored in memory, then other files or data has been stored after it. Now imagine you want to change one of the names in the list, for example Bill is now being replaced by Jenny. Jenny has more charters in her name than Bill so the change will not fit in the current memory location that was allocated for bill, the entire list would have to be moved to a new memory location and this would then leave a space in memory where the old list was. This is just one inefficiency of using a list that is not linked.

Array VS List: The terms List and Arrays are often used to describe the same thing, a standard static list, depending on which programming language you learned, whether you say Array or List you are probably referring to the same thing, here we will use the term Array to classify a standard static list/array.

ARRAYS VS LINKED LISTS
There are advantage and disadvantages of each, first we look at Arrays.
ARRAYS
Advantages:

Have an index for each element - this means you can go direct to the element you are looking for.

Disadvantage:

If the array is frequently changed it can be heavy on the memory

LINKED LISTS
Advantages:

Fast to add an item to the start of a list - the rest of the list does not need to change
Fast to delete an item to the start of a list - the rest of the list does not need to change
Is a flexible type of linear list due to how data is held

Disadvantages:

Slow to get to the element you want - needs to iterate through all elements until the element requested is found.
Maintenance of pointers can be complicated and time consuming.

Linked lists are a dynamic data structure containing nodes, pointers, a head and a terminator. The term 'node' refers to each part/location of the array. The term 'pointer' refers to the part of the node that point to another node, it actual terms it points to the memory location that that data is stored. The 'head' refers to the first node in the array and the 'terminator' the last node in the array.

SECTION 3 | SINGLE LINKED LISTS

Image illustrating a single linked list where each node has a link to the next node.

A singular linked list has a link from each node to the next node, it has a head node and a terminator/end node. This is the most basic type of linked list and the traversal between nodes can only go forward, from start to end, there is no way to travers back to a previous node.

SECTION 4 | DOUBLE LINKED LISTS

Image illustrating a double linked list where each node has a link to the next and previous node.

A double linked list has a pointer to the next node and a pointer to the previous node, this allows forward and backward traversal. This principle is often used on features such as forward and backward page navigation on web-browsers, with each node recording pages visited it is easy to navigate using the forward and back buttons. The same principle is also used on undo and redo features on various software.

SECTION 5 | CIRCULAR LINKED LISTS

Single Circular Linked List

Double Circular Linked List

Circular linked lists link the end of the list back to the start of the list.They are used for many applications that run on a continuous loop, such as:

A music playlist that is on repeat
A multiplayer gaming environment where the OS cycles through each player at a time in a loop.
Running multiple applications on a computer, the OS will cycle through each application giving it and allocated slot of time per cycle.

SECTION 6 | MODIFYING ELEMENTS OF A LINKED LIST

To modify items within a linked list it is important that you do not delete the pointer of previous or next nodes until a copy is made or they are no longer needed.
For the purpose of examination style questions it is important that you take a methodical approach to the process, giving structured step by step answers.

ADD AN ELEMENT

Use the following steps to add an item to a linked list:

1: Create the new node with the data to be added
2: Search the linked list to find the location where the new node should go
3: Set the pointer of the new node to the value held by the node before the location where the new node will be placed
4: Set the pointer of the previous node to the point to the new node being added

DELETE AN ELEMENT

Use the following steps to add an item to a linked list:

1: Search the linked list to find the location where the node needs to be deleted.
2: Set the node in the location before where the deleted item will be removed from to the value of the pointer held in the node to be deleted.
3: Delete the node

UPDATE AN ELEMENT

Use the following steps to add an item to a linked list:

1: Search the linked list to find the location where node to be modified is located
2: If found, modify the data within the node

ATTRIBUTE	ARRAY	LINKED LIST
MEMORY ALLOCATION	Arrays allocate memory in a contiguous block. This means the memory for all elements is allocated at one fixed location, usually at compile time for static arrays or at runtime for dynamic arrays. Since memory is contiguous, arrays have a fixed size, and resizing them (e.g., increasing their capacity) often requires allocating a new array and copying the data, which can be inefficient.	Linked lists allocate memory for each element separately, and each element (node) contains its own data and a reference (or pointer) to the next element in the sequence. This non-contiguous memory allocation allows for dynamic resizing. Memory can be allocated as needed at runtime, which is more flexible but can lead to greater memory overhead due to the storage of additional pointers.
ACCESS TIME	Provide fast access to elements using indices. Accessing an element at a specific index is a constant time operation (O(1)) This makes arrays ideal for applications that require frequent access to elements via their indices.	Have slower access times because elements are not indexed. To access an element, you must traverse the list from the beginning (or the end, in the case of a doubly linked list) until the desired element is found. Access time is linear (O(n)) making linked lists less efficient for direct element access.
INSERTION AND DELETION	Insertions and deletions are generally slower, especially for elements at the beginning or in the middle of the array, as shifting elements to maintain the array structure is required. These operations are O(n) in the worst case because of the need to shift elements to maintain order.	Excel in insertion and deletion operations. Since elements are linked with pointers, adding or removing elements only involves changing the pointers, not shifting elements. These operations can be O(1) if you're inserting or deleting at known positions (like the head of the list), but finding the position still requires O(n) time in singly linked lists.
MEMORY USAGE	More memory-efficient compared to linked lists as they do not require extra space for storing pointers. This compact layout can be beneficial in terms of memory caching and access speed.	Less memory efficient due to overhead from storing additional pointers for each element. The scattered nature of memory allocation can also impact performance due to increased cache misses.
USE CASES	Suitable for applications that require fast access based on index, such as lookup tables and matrices. Best when the number of elements is known ahead of time and changes infrequently.	Ideal for applications that require frequent insertion and deletion operations from the list without a fixed size constraint. Useful in situations where memory allocation needs to be flexible and allocated at runtime, like implementing stacks, queues, and other dynamic data structures.
EASE OF USE	Simpler to understand and use for beginners. They are supported directly with basic syntax in most programming languages.	More complex to implement correctly, especially when handling pointers and memory management. Often require more code to manage properly, increasing the risk of errors like memory leaks or pointer mismanagement.

What is a linked list data structure and how does it differ from an array data structure?
What is a singular linked list and how does it work?
What is a double linked list and how does it differ from a singular linked list?
What is a circular linked list and how does it differ from a singular linked list?
What is the advantage of using a linked list over an array in terms of insertion and deletion operations?
How can you traverse a linked list and access its elements?
How can you reverse a linked list using a double linked list?
What is a sentinel node in a linked list and what is its purpose?
How do you implement a linked list with a head and a tail pointer?
What is a self-circular linked list and how does it differ from a circular linked list?

ALSO IN THIS TOPIC

RECURSION
DATA STRUCTURES
LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS