From my series of Data Structure types and Big O Notation, Today I am going to talk about very important data structure in computer science Linked List. I will go in depth of explaining what advantages and disadvantages Linked Lists have in terms of data manipulation and Big O notation.
Before moving on, lets briefly discuss the definition of data structures. Data structure is a collection of values in some sort of containers, that enables us to store, manage, modify and manipulate data in an efficient way. There are many different types of data structures and all of them can work to get the job done. However, the trick is to choose the right data structure for a particular problem to speed up the work that takes less space or memory taken by the algorithm to run as a function. Different operations create various time and space complexity; therefore, it is important to utilize different data structures to ultimately achieve the best outcome.
Linked Lists and their Structure
A Linked List is a list that is linked. Hmmm.. That may not explain it well. Let’s discuss the fundamental of Linked Lists.
Linked List is a Linear data structure where each element(node) is a separate object. In other words, elements are not stored at a contiguous memory location. Instead, each element points to the next one. Linear structure is when the elements are attached to its previous and next adjacent, meaning that there is an order and sequence to how they are constructed and traversed. In order to get to the end of the list, we have to go through every element in the list sequentially. Linear structure is what makes Arrays and Linked Lists similar, therefore both of these cases order matters.
Linked List Structure
Each element in linked list contains two items — the data (or value) and a reference to the next element (also known as node). First element in the list is called Head, which only knows about itself (data it contains) and the next element. Second element or node knows only about itself and next node and so on. The last node points to the null or an empty value, since there is no element after it to point to. Exactly because of this structure, linked lists use dynamic data structure to allocate memory. Dynamic data structure means that it does not have given size and amount of memory pre-defined. While static data structures need a contiguous block of memory. For example, Arrays are static and their memory and size is pre-defined. Arrays need all of their resources to be allocated when the structure is created. This means that if we want to add more elements in the array, we’d need to recreate another array with bigger memory, copy the old memory data and then add new elements into it. On the other hand, dynamic data structures, such as linked lists, don’t have set amount of memory and can easily grow in size and memory.
Types of Linked Lists
There are three types of linked lists: Singly, Doubly, and Circular. The structure of a Singly linked list is the one described above, with the first element (head) pointing to the second, and last element pointing to null value. A doubly linked list has two references, one to the next node and another to previous node. Doubly linked lists are good if we want to traverse the data structure forward as well as backwards. Circular linked lists are great too, where last node of the list points to back to the first node (head) of the list.
source: https://slideplayer.com/slide/1608081/
Linked Lists and Big O Nation
Generally, linked lists are great for adding and removing elements, however it is very slow to search and access elements. Because of Linearity, the speed of accessing element is proportional to size of the list, which is Big O(n), traversing through the whole list. In this case, Arrays are great data structure and cost less to iterate or access index value. On the other hand, when adding a new node or element in the beginning of the list, we perform a single operation and Big O will be constant time, or Big O(1), similar to removing a node.
In the end, to compare Linked Lists to Arrays, Linked Lists are slow in search but faster in inserting and deleting elements (nodes). While, Arrays are great for random access, iteration, and traversing through list.
Resources:
