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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Farquan. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.25. You're not tied to anything after your purchase.
