Familiar With Arrays? But What About The Linked-List?

In computer science, the term data structure is used to describe a data organization and storage format that enables efficient access and modification. Simply put, the data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

There are many different types of data structures out there, but some of the most common are array, linked-list, binary-tree, hash-based structure, and graph, etc…In general, arrays are the simplest way to store data but the size of arrays in programming languages is usually fixed and the array is a contiguous list data structure, which means that memory cells are located one after the other in memory. The worst-case scenario when using arrays to find a particular element in it is O(n), for example, if you want to access the last element in the array, you have to traverse from the beginning to the end step-by-step. With a linked list, in a worst-case, you still have to traverse all the elements of the list before you find out the desired one. But there are some differences between an array and a linked list. Let’s find out in this article.

First, what is a list by the way?

Besides array, the list is another data structure that is used effectively when the size of data is dynamic and unknown and the list helps you overcome the weaknesses of arrays for those criteria.

Some of the forms of lists that can be implemented to work effectively with dynamic data are:

Linked-list
Stack
Queue

Linked-list is what we will dive in in this article, two other forms of list are Stack and Queue will be discussed in the next article.

What is a linked-list?

A linked list is a sequential-access data structure used for storing ordered elements that use non-contiguous memory locations to store data; each element in the linked list points to the next element in line and doesn’t have to be contiguous with the previous element. All linked lists are collections of node data structures that are connected by pointers – that’s where the “link” in “linked-list” comes from.

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Types of linked-List

There are plenty of types of linked-list, but primarily we have two types of linked-list as follow:

Single linked-list

In single linked-list, each node is the data we want to store and also the next pointer to determine what we will go next. Typically, a single linked-list is a one direction traverse.

Double linked-list

Similar to the single linked-list, each node is used to store data but including previous and next pointer to the vicinity node elements. Because double linked-list has previous and next pointer, so it supports both directions.

Essential vocal for linked-list:

Node: A data structure with two fields. One for data contains the information we want to store, and other is the next filed, which is a pointer and point to the next node in the linked-list. In a single linked-list, we just need next pointer to point to the next element, but with a double linked-list, we need previous and next pointer to traverse as well.
Pointer: A memory variable that points to a memory location. It is considered “where to go” address that point to the next element.
Head (head pointer): A pointer that points to the beginning of the first element in a data structure.
Null value: The absence of a value, meaning that there is no value stored here, we usually see it when starting a double linked-list and the ending of a list.
Tail: The last element in the linked-list, the next pointer of the tail element points to null to indicate the end of the list.
Size: The number of elements in a linked-list.

Linked list’s strengths and weaknesses

As I said before, linked-list is usually compared with array when they are both common types of data structure.

Strengths

A dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.
Deleting, updating and inserting are far easier than arrays. With arrays, we have to shift elements after deleting or inserting. A linked-list just has to update the address presents in the next pointer of a node.
Like mentioned at the beginning of this article, a linked-list allows for quick deleting or inserting with O(1).
The size of the linked-list can be changed or resized dynamically.
The size of a linked list is only limited by the amount of available memory.

Weaknesses of linked-list

Because each node in the linked-list contains a pointer, so we need extra memory for the pointer itself. So, more memory required to store elements comparing with arrays.
We cannot traverse the random-access element in linked-list as we do in the array by index. Linked-lists are sequential-access, which means, for example, if you want to access the n node, you have to traverse all nodes before it to get the desired location.
Reverse traversing is difficult especially in single linked-list, in case of doubly linked list it is easier but extra memory is required for back pointer hence wastage of memory.

Common Operations Cheat Sheet

Operation	Description	Time complexity	Mutates structure
`find(value)`	Returns a pointer to the `node` containing `value` in the data field, or NULL if it isn’t in the list. This method can be used for `membership checking` as well.	O(N)	No
`find(index)`	Returns a pointer to the `index`th node from the head pointer, or NULL if `index` is longer than the length of the list.	O(index)	No
`addBeginning(value)`	Adds a new node with a data field containing `value` to the beginning of the list	O(1)	Yes
`addAfter(value, n)`	Adds a new node with a data field containing `value` after node `n`	O(1)	Yes
`remove(value)`	Removes first instance of value from list	O(N) if we need to find the element.	Yes
`removeNextElement(n)`	Removes node after `n`	O(1)	Yes
`removeThisElement(n)`	Removes node `n`	O(1) on doubly linked-list	Yes

Linked-list’s code example:

Below are some of the examples about linked-list consist of single linked-list and also double linked-list, which I will implement in JavaScript language.

Single linked-list:

First, I will create two constructor Node and SingleList . The first one will be responsible for store data and point to another node. To implement this purpose, we need to to create two properties, data and next, respectively and we will pass data as a parameter:

function Node(data){
    this.data = data;
    this.next = null;
}

Then we will create another constructor, SingleList, each instance of SingleList will have two properties _length and head (‘_‘ which is frequently used to preface the name of an object’s property or method that is private). Since every new instance of SinglyList does not contain a node, the default value of head is null and the default value of _length is 0:

function SinglyList() {
    this._length = 0;
    this.head = null;
}

Let’s go a little further and see how we can add a value in a linked-list:

function SinglyList() {
  // head will be the top of the list
  // we'll define it as null for now
  this.head = null;
  this.length = 0;
  
    this.add = function(data) {
    var nodeToAdd = new Node(data),
        nodeToCheck = this.head;
    // if the head is null
    if(!nodeToCheck) {
      this.head = nodeToAdd;
      this.length++;
      return nodeToAdd;
    }
    // loop until we find the end
    while(nodeToCheck.next) {
      nodeToCheck = nodeToCheck.next;
    }
    // once were at the end of the list
    nodeToCheck.next = nodeToAdd;
    this.length++;
    return nodeToAdd;
  }
}

There are many things just happened in this code above, let’s break things down:

At the top, we define some properties at the top when for when the list id first created. It’ll start with zero nodes and those properties reflect that.
Then we defined the add method. This starts by creating a new node to add and sets nodeToCheck as the first node in the list.
We check if it’s the first node in the single linked-list by using the if statement. This should only ever fire once. It sets the head for us and we increment the length. Or, we drop down the while statement.
This takes us to the end of our list by setting the nodeToCheck to the next node in the list until there are no more. We know we’re at the end, so we add it to next, increment length, and we bounce out of there.

Conclusion

Oh, wee. So it’s enough for this article. Linked-list is one of the common data structures besides arrays that is mostly used when we don’t know exactly the element size and the size could be changed dynamically. Its advantages and disadvantages comparing with arrays we already talked about above. Head, pointer, node, data, next, previous are important vocabs when dealing with linked-list. We’ve been through discussing 2 types of linked-list, which are single linked-list and double linked-list, the double one is more flexible than the single one. Learn how to use a linked list is so important especially before taking an interview.

Facebook0 Tweet0

Familiar With Arrays? But What About The Linked-List?9 min read