Linked List

Linked List Definition


A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Pointers are used to link elements. Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location. Linked List also has some advantages over arrays such as dynamic size and easier insertion or deletion. Linked list can be visualized as a chain of nodes, where every node points to the next node.
These are the basic operations supported by a list.
  • Insertion − Adds an element at the beginning of the list
  • Deletion − Deletes an element at the beginning of the list
  • Display − Displays the complete list
  • Search − Searches an element using the given key
  • Delete − Deletes an element using the given key

Linked List

Types of Linked List


  • Simple Linked List − Item navigation is forward only
  • Doubly Linked List − Items can be navigated forward and backward
  • Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous

Double Linked List

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily. 
Following are the basic operations supported by a list.
  • Insertion − Adds an element at the beginning of the list
  • Deletion − Deletes an element at the beginning of the list
  • Insert Last − Adds an element at the end of the list
  • Delete Last − Deletes an element from the end of the list
  • Insert After − Adds an element after an item of the list
  • Delete − Deletes an element from the list using the key
  • Display forward − Displays the complete list in a forward manner
  • Display backward − Displays the complete list in a backward manner
Doubly Linked List

Circular Linked List
Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.
Following are the important operations supported by a circular list.
  • insert − Inserts an element at the start of the list
  • delete − Deletes an element from the start of the list
  • display − Displays the list



Singly Linked List as Circular


In singly linked list, the next pointer of the last node points to the first node.
Singly Linked List as Circular Linked List

Doubly Linked List as Circular


In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.
Doubly Linked List as Circular Linked List












Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Image
Binary Search Tree Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.  It is called a Binary tree because each tree node has a maximum of 2 children It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. The properties that separates a binary search tree from a regular binary tree is All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs meaning they have the above two properties On the picture shown above, the right tree is not a binary search tree because on the right subtree of the root, there's a number with smaller value than the root.  Basic Operations Following are the basic operations of a tree − Search   − Searches an element in a tree. Insert  − Inserts an element in a tree. Pre-order Traversal  − Traverses a tree in a pre-order manner...
Read more

Hashing Table & Binary Tree

Image
Hashing Table Hash Table is a data structure which stores data in an associative manner.  Data is stored in an array format, where each data value has its own unique index value.  Access of data becomes very fast if we know the index of the desired data. So,   Hash Table is a data structure in which insertion and search operations are very fast where the size of the data doesn't matter.   Hash Function  A hash function job is to store values in an array with a limited size It does it in a way that the array doesn't need to be searched through to find it. This allows us to enter values in any order and we can find them using a calculation instead of searching through the array So how does Hash Table & Hash Function work together? Key values are assigned to elements in a Hash Table using a Hash Function Hash function helps calculate the best index an item should go in Here are a few methods to hash  keys  from string: Mid...
Read more

AVL Tree & B - Tree

Image
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.  Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor . Balance Factor Balance factor of a node in an AVL tree is the differenc e between the height of the l eft subtree  and that of the  right subtree  of that node Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. If the difference in the ...
Read more