Class: Computer Science
Farhan Shaikh
Date: 04/11/2021
Thursday 4 Topic: Data structures and linked
November 2021 lists
Essential
Data structures and linked lists
Main Ideas / Key Words Notes
What is a linked list? A linked list is a data structure that provides a foundation upon which
other structures can be built, such as stacks, queues, graphs, and
trees.
• A linked list is constructed from nodes and pointers.
• A start pointer identifies the first node. Each node contains data
and a pointer to the next node.
• Many programming languages support lists in addition to arrays.
•Data in lists can be stored anywhere in memory, with pointers
indicating the address of the next item.
Implementing linked lists in an array
• A linked list can be implemented using a static array.
• Being static data structures, arrays are stored contiguously in
memory, requiring the use of an index register to determine where a
specific index is in relation to a base address.
• Items are stored in the array in contiguous order —
• However, in the linked list, the items are being stored
alphabetically because of their pointers.
Implementing linked lists using object
• While a linked list can be implemented using a static array, its true
benefit becomes evident when using object-oriented techniques.
• With a linked list that uses objects, any available memory address
can be used to store data. It does not need to be adjacent, as each
node points to the next in the structure.
• The memory footprint of the data structure is not determined at
compile time and can change dynamically at runtime, referred to as a
dynamic data structure.
Linked lists applications
• Linked lists can be used by:
o Operating systems managing a processor to store process blocks in
a ready state.
o Image viewers to switch between previous and next images.
o Music players to store tracks in a playlist.
o Web browsers to navigate backwards and forwards.
• Linked lists could also be used:
o For hash table collision resolution as an overflow. o Maintaining a
What operations can be performed in a linked file allocation table of linked clusters on secondary storage.
list?
Add: Adds a node to the linked list
Delete: Removes a node from the linked list
Next: Moves to the next item in the list
Previous: Moves to the previous item in a doubly linked list
Traverse: A linear search through the linked list
Summary
A linked list is a data structure where the objects are arranged in a linear order. Unlike an array, however, in which
the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.
Linked lists differ from lists in the way that they store elements in memory. While lists use a contiguous memory block
to store references to their data, linked lists store references as part of their own elements.
Farhan Shaikh
Date: 04/11/2021
Thursday 4 Topic: Data structures and linked
November 2021 lists
Essential
Data structures and linked lists
Main Ideas / Key Words Notes
What is a linked list? A linked list is a data structure that provides a foundation upon which
other structures can be built, such as stacks, queues, graphs, and
trees.
• A linked list is constructed from nodes and pointers.
• A start pointer identifies the first node. Each node contains data
and a pointer to the next node.
• Many programming languages support lists in addition to arrays.
•Data in lists can be stored anywhere in memory, with pointers
indicating the address of the next item.
Implementing linked lists in an array
• A linked list can be implemented using a static array.
• Being static data structures, arrays are stored contiguously in
memory, requiring the use of an index register to determine where a
specific index is in relation to a base address.
• Items are stored in the array in contiguous order —
• However, in the linked list, the items are being stored
alphabetically because of their pointers.
Implementing linked lists using object
• While a linked list can be implemented using a static array, its true
benefit becomes evident when using object-oriented techniques.
• With a linked list that uses objects, any available memory address
can be used to store data. It does not need to be adjacent, as each
node points to the next in the structure.
• The memory footprint of the data structure is not determined at
compile time and can change dynamically at runtime, referred to as a
dynamic data structure.
Linked lists applications
• Linked lists can be used by:
o Operating systems managing a processor to store process blocks in
a ready state.
o Image viewers to switch between previous and next images.
o Music players to store tracks in a playlist.
o Web browsers to navigate backwards and forwards.
• Linked lists could also be used:
o For hash table collision resolution as an overflow. o Maintaining a
What operations can be performed in a linked file allocation table of linked clusters on secondary storage.
list?
Add: Adds a node to the linked list
Delete: Removes a node from the linked list
Next: Moves to the next item in the list
Previous: Moves to the previous item in a doubly linked list
Traverse: A linear search through the linked list
Summary
A linked list is a data structure where the objects are arranged in a linear order. Unlike an array, however, in which
the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.
Linked lists differ from lists in the way that they store elements in memory. While lists use a contiguous memory block
to store references to their data, linked lists store references as part of their own elements.
