Linked Lists

What is a Linked List?

A Linked List is a collection of objects that have been added in a particular order and we want to maintain that order. The objects that we want to maintain the order of is an ordered collection of nodes. Each node contains the data stored and a link to the next node. The data can be any valid data type. Each node points or links to the next and previous node. A Linked List uses links to create this collection of ordered objects. It does this by creating a kind of “chain link” of nodes. The list holds a link to the first node and the last node. The list can be traversed by starting at one of these nodes and then following the links to other nodes.

Very similar to arrays, linked lists store elements in sequential order. Unlike arrays, elements are not stored in a particular location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list Instead of keeping indexes, linked lists hold pointers to other elements. The first node is called the head while the last node is called the tail.

Types of Linked Lists

In a singly-linked list, each node only has one link that points to the next node. In a singly-linked list, the head is where we begin our journey down the rest of the list.

In a doubly-linked list, a link to the previous node is also kept. Therefore, we can also start from the tail and traverse backward toward the head.

A circular -linked Lists acts as a variation of a linked list in which the last node points to the first node or any other node before it, thereby forming a loop.

Why Linked Lists?

Using linked lists have some advantages, nodes can easily be removed or added from a linked list without reorganizing the entire data structure. This is a major advantage over using arrays.

A disadvantage of using a linked list over an array is search operations are much slower in linked lists. Random access of data elements is not allowed like they are in arrays. Nodes are accessed sequentially starting from the head node to the tail node.