Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

Advantages and Disadvantages of Linked List

Advantages of Linked List

  1. The linked list is a dynamic data structure.
  2. You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at run-time itself.
  3. In this, you can easily do insertion and deletion functions. That is, you can easily insert and delete the node.
  4. Memory is well utilized in the linked list. Because in it, we do not have to allocate memory in advance.
  5. Its access time is very fast, and it can be accessed at a certain time without memory overhead.
  6. You can easily implement linear data structures using the linked list like a stack, queue.

Disadvantages of Linked List

  1. The linked list requires more memory to store the elements than an array, because each node of the linked list points a pointer, due to which it requires more memory.
  2. It is very difficult to traverse the nodes in a linked list. In this, we cannot access randomly to any one node. (As we do in the array by index.) For example: - If we want to traverse a node in an n position, then we have to traverse all the nodes that come before n, which will spoil a lot of our time.
  3. Reverse traversing in a linked list is very difficult, because it requires more memory for the pointer.

Application of Linked List

The linked list is a primitive data structure, which is used in various types of applications.

  1. It is used to maintain directory names.
  2. The linked list can perform arithmetic operations in the long integer.
  3. Polynomials can be manipulated by storing constant in the node of the linked list.
  4. We can also use it to next and previous images in the image viewer.
  5. With the help of the linked list, we can move songs back and forth in the music player.
  6. The linked list is also used for undo in word and Photoshop applications.
  7. All the running applications in the computer are stored in the circular linked list, and the operating system provides them with a fixed time slot.
  8. It can also be used to implement hash tables.

Difference between linked list and array

Both array and linked list are used to store the same type of linear data, but array is allocated contiguous memory location in the compile-time while the linked list is allocated memory in run-time.

ArrayLinked List
It is a collection of the same type of data type.  It is a collection of similar elements that are connected to each other by the pointers.
It supports random access, which means that we can access it directly using its index, like arr[0] for 1st element, arr[7] for the 8th element, etc.It supports sequential-access, meaning that in order to use any node in it, the user must traverse the whole list sequentially.
In the array, elements are stored in the contiguous-memory location.The elements in the linked list can be stored anywhere in memory.
The time complexity of the array is O (1).The time complexity of the linked list is O (n).
It is allocated the memory at compile-time.It is allocated the memory at run-time.
Arrays take longer to perform insertion and deletion functions than linked lists.In the linked list, both insertion and deletion operations take less time than the array.
It can be a 1-d array, 2-d array, or 3-d array.It can be a linear linked list, doubly linked list, or circular linked list.