Liked list

Abstract

A linked list is an abstract data structure where the elements can be easily inserted or removed without reallocation or reorganization of the entire structure?because the data items do not need to be stored contiguously in memory or on disk in opposition to an array data structure.

Main concepts

The implementation of a linked list is implemented by the Object-Oriented-Programming paradigm. our main class will be the list that will contain all our nodes, and the second class will be the node itself. the specific implementation of our list is dependent on the problem we are trying to solve. in this article, we are going to implement the Stack and Queue data structures.

Computer operations

As I mentioned above the operation of an array and a linked list is different when we focus on space efficiency. when we are heading to deal with an array data structure our computer will point only to the "head" of our array, also known as the first index. in this case, we simply can't divide our array items into different places in our memory because we will lose data in the garbage collector automatically but we have an advantage to an array which is the indexing, that kind of attribute is not part of the linked list data structure and because of such a fantastic attribute, we can develop sophisticated searching and sorting algorithms, but the downfall of the array comes when we are thinking about memory allocation and this is where a linked list can come in very handy.

A linked list as opposed to an array does not rely on the idea of contiguous data allocation. the head of the list can be allocated in memory space: x07 where the next node can be in x03, as in an array if the next space in the memory is taken by another variable or something else, the array will copy itself to another place. just think of a situation where you have a million items in your array, this kind of operation is very inefficient, but in a linked list each node will simply point to the next allocation in the memory of the next node.

Stack

A stack is a practical implementation of a linked list where the main concept of this data structure is the First-In-Last-Out. think about a Stack like an array where the main operations are push(value) and pop() of the last inserted node but we are getting the advantage of a linked list memory allocation. this is the basics of Stack creation:

• Node: contain its value and a pointer to the next node.
• Stack: contain all our nodes where the top node will be the first to get out.
• Push: Will add to the top of the list the given node, so our new "top" is the inserted value and its next value will be the last top that has been there.
• Pop: Will delete the top node from the list and re-assign the top as the second to the full node.

Queue

A queue is actually pretty similar to a stack data structure but the main difference is that we actually implementing the First-In-First-Out this time. think about a queue just like a real queue in line in which the first person who arrived will get the service first. but in a more practical computer example, it's similar to push and shift() in an array but again we get the advantage of a linked list memory allocation. this is the basics of Queue creation:

• Node: contain its value and a pointer to the next node.
• Stack: contain all our nodes where the front node will be the first to get out, and our back node will be the last one.
• Enqueue: Will add to our list a node to the end of our order in the queue and that node will be the last to execute.
• Dequeue: Will execute and return the front node of our queue AKA the first node in our list.

Use cases

The use cases of a specific data structure can vary in a lot of ways but they are probably about to repeat themselves in some use cases, for example:

Stack: reversing, undoing, and testing symmetry. Queue: managing requests on a single shared resource such as CPU scheduling and disk scheduling, handling hardware or real-time systems interrupts, handling website traffic, routers and switches in networking, and maintaining the playlist in media players.

Conclusions

A linked list data structure is not always useful for developing a production software, sometimes it can cause over-maintenance of the data structure when we are dealing with languages where the data structure is not pre-implemented such as JavaScript where you need to create it from scratch in oppose to Java where you have a LinkedList built-in class implementation. but there are some cases where it is beneficial to use a linked list for example when you need to loop the whole collection of items to execute a certain repeated work, in this case maybe it is better to use a linked list because we are not losing the indexing advantage of an array data structure for the reason we are not using any sorting/searching algorithm an only doing an O(n) linear search, and in that case, the memory allocation of our linked list is a big advantage.