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.
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.
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.
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.
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
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?
