Data Structures: Linked List

Software Development
#1

Definition

A Linked List is a sequential list of nodes (Objects) containing data and pointing to another (usually the next) node that also contains data.
Below is a list of terms we use when talking about linked lists and their corresponding definitions.

Head: is the first node in a linked list, it points to the first next node in the list.

Tail: is the last node in a linked list, it points to null.

Pointer: is the reference of the next node.

Node: is an object containing data and a pointer to another node.

Linked lists keep a reference of their Head and Tail nodes to make it easier to add and remove nodes.

Usage

1- Used in Lists, Queue, and Stack implementations.

2- For creating circular lists, modeling repeating event cycles.

3- For modeling real-world objects.

4- For hashtable separate chaining.

5- For implementing adjacency lists for graphs.

Types

There are two main types of linked lists, singly and doubly.

1260×196 3.52 KB

Singly linked-lists hold a reference to the next node only, whether the doubly linked-lists hold two references one for the next node and another for the previous node.

1400×170 23.7 KB

Pros and Cons

While Singly linked-lists are easier to implement and use less memory, they don’t offer easy access to previous nodes.

On the other hand, doubly linked-lists can be traversed backward, yet they occupy 2 times space in memory.

Time Complexity

Different operations in a Liked List have different time complexities. the table below shows the big O notation for the different possible operations in both singly and doubly linked-lists.

921×895 60.7 KB

#2

A linked list is a linear data structure and also a sequential data structure

But it doesn’t allow random access.

A linked list is better from an array in some cases

If we don't know the size of the array
If we wanna insert an element at the beginning of array!
If we wanna implement queue and dequeue data structure.
If we wanna delete an element from the middle of the array!
Merge sort is better in the linked list because of less space complexity.