A Discussion on Singly Linked List
What are Linked Lists?
The data structure for grouping and storing similar items together in most programming languages is used as an array, also known as a list. An array is a linear data structure that stores items together contiguously in memory. A linked list is similar to an array in that it also is a linear data structure, however, linked list stores information non-contiguously in memory. Since arrays store information in a contiguous block of memory when creating and manipulating the array often times will result in having too much or too little memory allocated to it. Linked list is much better at memory utilization in that it stores information non-contiguously in memory and only uses memory when needed.
Linked List Versus Array
Although linked lists are great at memory utilization they do have some drawbacks to regular arrays. Linked lists are great at inserting and removing items from the beginning and the end, however, they lagged when accessing the item due to the fact that nodes must be traversed starting from the beginning to look for the interested item.
Basics of Linked List
A linked list has a chain of nodes. A node is a unit of information, in a linked list it will typically consist of the data and the next pointer. They are chained together by each node having a reference property that points to the following node, in this case it’s called the “next pointer” property. The first node is the starting node and it is set as the head node. The last node in the linked list will have a next pointer property of Null or None because it’s the last node in the list and there aren’t any nodes after that. Often times linked lists are compared to a freight train, where each connecting freight car is like a node in a linked list. And the caboose is the tail of the node and the head of the node is the engine car.
Diagrams of Array and Linked List
To get a better understanding of linked lists, below is a diagram implementing data with values of 23, 4, 65, and 7 in a typical dynamic array.
Notice the memory addresses when implementing the data as an array — they are contiguous and sequential, storing one right after another.
Now storing the same data as a linked list would look something like this:
Note how the linked list uses memory as needed, or dynamically, as when new nodes are created and the memory addresses for each node is randomly assigned. Conversely, when using a dynamic array, the memory addresses are sequential and extra memory at the end is allocated upon data creation to handle the possibility of inserting new values.
Linked List Implementation
A basic linked list has a head and tail properties. Typically there’s also a size property that increment or decrement when nodes are added and deleted, respectively, to keep track of the size of the linked list.
To add/append an item/value to the list, a node needs to be created and setting the tail node’s next property to be the new node, and updating the tail property to be that new node. Since all steps to add a node to the linked list require constant time, the time complexity of this method is O(1), which is similar to a dynamic array. However, since during the creation of a dynamic array only a select amount of extra memory is allocated to it and when it is all filled up, the array needs to be copied, or reallocated to a new slot in memory causing the time complexity of O(2n) or reducing down to O(n). Because most of the time adding an item to a dynamic array takes O(1) time and sometimes O(n), its time complexity of O(1) is considered amortized whereas a linked list will always be O(1).
Accessing data in an array is simple and fast because each element in the array is assigned an index. For example, in our example above calling sample_list with index 2 will instantly give us the value of 65. As such accessing an item in an array takes constant time. Accessing data from a linked list requires a bit more work. Linked list have no indexes and to get to the data you are requesting you must traverse through the nodes and see if it’s the data you are looking for. Traversing a linked list always starts that the head because each node only has information about its data and its next node, and nothing more, which is why it’s not possible to start traversing in the middle of the linked list. Since nodes must be traversed in order to access data the time complexity is O(n), where if you were to access an item near the tail end of the linked list.
To find an item/value in the linked list you must traverse through the nodes and compare each node along the way if the data is what you are looking.
Since the only way to traverse a linked list is by the starting at the head, there’s a possibility all nodes must be traversed in order to find the value you are looking for thus its time complexity is O(n).
The process to insert /delete items in the middle of the linked list expands on the steps of the find method with steps to reset next pointers to the appropriate nodes in order to update the linked list. The time complexity of insert/delete is O(n) because while it is an expansion of the find method all additionally steps take constant time so its time complexity is the same as the find method. A visual representation from Visalgo.com.
As with any data structures there are advantages and disadvantages to using them and linked lists are no different. They a have time complexity of O(1) to insert and delete at the beginning and end, which make those processes extremely fast. However, they suffer when trying to find the node’s index, and deleting a node in the middle of the linked list. A linked list is just another tool a developer can use to make better programming choices to optimally balance runtime and memory usage for their projects.
The complete implementation of a linked list can be found at gitHub.
Sources:
