This content originally appeared on Level Up Coding - Medium and was authored by ayt
Table Of Contents
— Why do we use Linked Lists over arrays?
— Advantages & Disadvantages of Linked Lists
— Code Implementation of a Linked List in Python
— Real-life use cases of Linked Lists
Why do we use Linked Lists over arrays?
Before we talk about Linked lists, we have to know what is an array first. An array is a collection of elements of the same type stored in contiguous memory locations. The reason why we use Linked lists is because it can overcome the limitations of arrays.
One of the most significant limitations of arrays is their fixed size. When creating an array, the size must be declared in advance, which can be problematic if you don’t know how many elements you need. Moreover, if you want to add or delete an element, you have to move all the elements after the addition or deletion to make space, which can be time-consuming if there are so many elements like millions of them inside an array.
Linked lists can allocate memory dynamically, allowing them to grow or shrink as needed. This means that you don’t need to know the size of the linked list beforehand, and you can easily add or delete elements without worrying about moving other elements.
What is a Linked List?
A linked list is a collection of nodes, or elements, that are stored randomly in memory. Each node contains data and a pointer to the memory address of the next node in the list.
We will talk about how a singly linked list works first and then move on to a doubly linked list. Each singly linked list has the data and ONLY ONE pointer that contains the memory address of the next element. As you can see in the image, there are nodes, and each node has data (A, B, C, D ) and addresses of the next element. Note that we can only search elements starting from the head ( one-way ) unlike a doubly linked list where we can search elements either from the head or tail.
As you can see from the image, we have to update the memory addresses of elements whenever we add or delete elements. In this example, we will update the pointer of “C” to the new element (“?”) which will take the position of D. After updating the memory address of the “C”, the pointer of a new element (“?”) will now point at “D”.
When deleting an element, we also have to upgrade the addresses of elements. In this case, if we want to delete “C”, we will have to upgrade the pointer of “B” to point at “D”. As you might notice, deleting and adding is really fast in linked lists unlike in arrays, where we have to loop the whole thing just to add or delete like in array. For linked lists, adding and deleting time is O(1), and searching time is O(n).
Doubly Linked List
One of the key features of a doubly linked list is that each node in the list has two memory addresses: one for the next node in the list, and one for the previous node. This means that you can traverse the list in either direction, starting from either the head or the tail.
For example, let’s say you have a doubly linked list of student records, sorted alphabetically by last name. If you wanted to find the record for a specific student, you could start at either the beginning or the end of the list and traverse it in the appropriate direction until you find the record you’re looking for.
However, there is a downside to using doubly-linked lists: they use more memory than singly-linked lists since each node has to store two memory addresses instead of just one. This can become an issue if you’re working with large amounts of data, or if memory usage is a concern for your particular application.
Advantages & Disadvantages
One of the advantages of linked lists is their memory efficiency. Compared to arrays, linked lists can save memory in certain cases, especially when the size of the list is not known in advance. Linked lists are also dynamic in size, meaning they can grow or shrink as needed during program execution, which is not the case with arrays that have a fixed size. Additionally, linked lists allow for efficient insertion and deletion of elements anywhere in the list because you only need to update the pointers of a few nodes, whereas with arrays you may need to shift all the elements after an insertion or deletion.
However, linked lists also have some disadvantages. One major disadvantage is that they don’t support random access to elements like arrays do. This means you need to traverse the entire list to find a specific element, which can be slow for large lists. Another disadvantage is that linked lists require extra memory to store the pointers between nodes, which can be a disadvantage if memory usage is a concern.
Code Implementation
# Creating a node class
class Node:
def __init__(self, item):
self.item = item
self.next = None
# Creating a linked list class
class LinkedList:
def __init__(self):
self.head = None
# Creating a linked list object
linked_list = LinkedList()
# Adding items to the linked list
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
# Connecting the nodes
linked_list.head.next = second
second.next = third
# Printing the items in the linked list
current_node = linked_list.head
while current_node is not None:
print(current_node.item, end=" ")
current_node = current_node.next
>>> output: 1 2 3
Real-life use cases
Image editing software uses linked lists to manage the undo/redo history of user actions. Each node in the list contains a snapshot of the image and pointers to the previous and next snapshots. This allows users to easily undo or redo their changes by simply traversing the linked list.
Another example of how linked lists are used in software is in music players. Music players use linked lists to manage playlists. Each node in the list contains the name of a song and pointers to the previous and next songs in the playlist. This allows users to easily navigate their music library and listen to their favorite songs in a specific order.
Linked lists are also used in many other applications, such as web browsers to manage browser history, in operating systems to manage process queues, and in GPS systems to store directions between locations.
I hope this blog has helped you gain a better understanding of linked lists. As always, thank you for taking the time to read it. If there is anything you want to correct, feel free to correct me as I am willing to learn more and more from my mistakes.
You can keep in touch with me on Twitter: https://twitter.com/Ayt06153394
Linked Lists in Data Structure was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by ayt
ayt | Sciencx (2023-05-01T02:52:23+00:00) Linked Lists in Data Structure. Retrieved from https://www.scien.cx/2023/05/01/linked-lists-in-data-structure/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.