Linked list Data Structure

Hi everyone, inside this article we will see the concept about Linked list Data Structure.

A linked list is a data structure in computer science that consists of a sequence of data elements, which are connected together via links. Each data element, called a node, contains a reference, or link, to the next node in the list. This allows for efficient insertion and deletion of elements, as only the links between the elements need to be updated, rather than the elements themselves.

There are two types of linked lists: singly linked lists and doubly linked lists.

In a singly linked list, each node has a link to the next node in the list, but not to the previous one. In a doubly linked list, each node has a link to both the next and previous nodes in the list.

Characteristics of Linked List

The characteristics of a linked list in Data Structure and Algorithms (DSA) are:

1. Dynamic size: Linked lists can grow or shrink in size during runtime, unlike arrays which have a fixed size.
2. Efficient insertion and deletion: Inserting or deleting a node in a linked list only requires updating the links between the nodes, rather than shifting elements in an array.
3. Linear data structure: Linked lists are linear data structures, meaning that the elements are arranged in a single sequence.
4. Sequential access: To access an element in a linked list, you must traverse the list from the head to the desired node, one node at a time.
5. Extra memory: Linked lists require extra memory to store the links between the nodes, in addition to the data stored in the nodes.
6. No random access: Linked Lists don’t support random access, as all nodes have to be traversed, in order to access any specific node.
7. Singly and Doubly linked lists: Linked lists can be implemented as either singly linked lists or doubly linked lists, where each node has a link to the next node in singly linked list and links to both next and previous node in doubly linked list.
8. Head and Tail: The first node in a linked list is called the head and the last node is called the tail.
9. Applications: Linked lists can be used to implement various data structures such as stacks, queues, and associative arrays.

Representation of Linked List

Linked list represented by using

• A data item
• An address of another node

We wrap both the data item and the next node reference in a struct as:

struct node
{
  int data;
  struct node *next;
};

Let us create a simple Linked List with three items to understand how this works.

Linked List Implementations in C++

// Linked list implementation in C++

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// Creating a node
class Node {
   public:
  int value;
  Node* next;
};

int main() {
  Node* head;
  Node* one = NULL;
  Node* two = NULL;
  Node* three = NULL;

  // allocate 3 nodes in the heap
  one = new Node();
  two = new Node();
  three = new Node();

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // print the linked list value
  head = one;
  while (head != NULL) {
    cout << head->value;
    head = head->next;
  }
}

Output

Types of Linked list data structure

There are several types of linked list data structures, including:

1. Singly Linked List: A singly linked list consists of a sequence of nodes, each of which contains a value and a pointer to the next node in the sequence. The last node in the list has a pointer to null. This type of linked list is the simplest and most common type.
2. Doubly Linked List: A doubly linked list is similar to a singly linked list, but each node contains a pointer to both the next and previous nodes in the sequence. This allows for easier traversal in both directions, but requires more memory for the extra pointer in each node.
3. Circular Linked List: A circular linked list is similar to a singly or doubly linked list, but the last node in the list has a pointer to the first node, creating a circular sequence. This allows for easier traversal when the list needs to be processed continuously.
4. Sorted Linked List: A sorted linked list is a singly or doubly linked list in which the nodes are arranged in order according to the value they contain. This makes searching for a specific value more efficient.
5. Skip List: A skip list is a more complex type of linked list that uses multiple layers of linked lists with varying spacing between nodes to provide a faster search time. This type of linked list is often used in large-scale databases.

These are some of the most common types of linked list data structures. Each type has its own advantages and disadvantages, and is suitable for different types of applications.

We hope this article helped you to understand Linked list Data Structure, Characteristics, etc in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.