Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  • Types of Linked Lists
  • Example
  • Operations of the Linked Lists in data structure
  1. Data Structure

Linked Lists

A Linked List is a linear data structure where elements are not stored at contiguous memory locations but are linked using pointers. Each element, known as a node, consists of two parts: the data and a reference (link) to the next node in the sequence. This allows for efficient insertions and deletions, as you only need to update the references of the nodes and not move entire sections of data around. However, this also means that access times can be slow as you have to traverse the list from the head node to find the element you want. Linked lists are used in many data structures and algorithms, like stacks, queues, graphs, and hash tables.

Types of Linked Lists

There are four types of Linked Lists:

  • Singly Linked List: It is the simplest type of linked list, where each node contains some data and a pointer to the next node of the same data type. This allows traversal of data only in one direction.

  • Doubly Linked List: A more complex type of linked list that contains a pointer to the next as well as the previous node in sequence. This enables us to traverse the list in both forward and backward directions.

  • Circular Linked List: In this type of linked list, the last node points back to the first node, making a circular loop.

  • Doubly Circular Linked List: This is a more complex type of linked list where the last node points back to the first node and the first node also points to the last node, making it circular. Also, each node has a pointer to its next and previous node, making it doubly linked.

Example

// Singly Linked List:
public class Node
{
    public int data;
    public Node next;

    public Node(int i)
    {
        this.data = i;
        this.next = null;
    }
}

var list = new SinglyLinkedList();

Operations of the Linked Lists in data structure

There are some operations of the Linked Lists in the data structure:

  • Traversal: Access each element of the linked list.

  • Insertion: Adds a new node to the linked list. You can add elements to either the beginning, middle or end of the linked list.

  • Deletion: Removes an existing node from the linked list. You can delete either from the beginning, end or from a particular position.

  • Search: Finds a particular node in the linked list.

  • Update: Modifies the value of a node.

  • Sort: Arranges nodes in a specific order.

Complexity Table

Operation
Best Case
Average Case
Worst Case

Access

O(N)

O(N)

O(N)

Search

O(N)

O(N)

O(N)

Insertion (at the beginning)

O(1)

O(1)

O(1)

Insertion (at the end, with a tail pointer)

O(1)

O(1)

O(1)

Insertion (at the end, without a tail pointer)

O(N)

O(N)

O(N)

Insertion (in the middle)

O(N)

O(N)

O(N)

Deletion (from the beginning)

O(1)

O(1)

O(1)

Deletion (from the end, with a tail pointer)

O(N)

O(N)

O(N)

Deletion (from the end, without a tail pointer)

O(N)

O(N)

O(N)

Deletion (from the middle)

O(N)

O(N)

O(N)

Update

O(N)

O(N)

O(N)

PreviousArrayNextStacks

Last updated 1 year ago