Introduction to Linked Lists

-

Introduction to Linked Lists

Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence.
Each node holds its own data and the address of the next node hence forming a chain like structure.
Linked Lists are used to create trees and graphs.
Linear Linked List

Advantages of Linked Lists

  • They are a dynamic in nature which allocates the memory when required.
  • Insertion and deletion operations can be easily implemented.
  • Stacks and queues can be easily executed.
  • Linked List reduces the access time.

Disadvantages of Linked Lists

  • The memory is wasted as pointers require extra memory for storage.
  • No element can be accessed randomly; it has to access each node sequentially.
  • Reverse Traversing is difficult in linked list.

Applications of Linked Lists

  • Linked lists are used to implement stacks, queues, graphs, etc.
  • Linked lists let you insert elements at the beginning and end of the list.
  • In Linked Lists we don't need to know the size in advance.

Types of Linked Lists

There are 3 different implementations of Linked List available, they are:
  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List
Let's know more about them and how they are different from each other.

Singly Linked List

Singly linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in the sequence of nodes.
The operations we can perform on singly linked lists are insertion, deletion and traversal.
Linear Linked List

Doubly Linked List

In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.
Double Linked List

Circular Linked List

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
Circular Linked List

We will learn about all the 3 types of linked list, one by one, in the next tutorials. So click on Nextbutton, let's learn more about linked lists.

Comments

Post a Comment

Thanks for comment. We will get back to you soon...

Popular posts from this blog

Difference between Array and Linked List

-
Image
Linked List vs. Array Array is a datatype which is widely implemented as a default type, in almost all the modern programming languages, and is used to store data of similar type. But there are many usecases, like the one where we don't know the quantity of data to be stored, for which advanced data structures are required, and one such data structure is  linked list . Let's understand how array is different from Linked list. ARRAY LINKED LIST Array is a collection of elements of similar data type. Linked List is an ordered collection of elements of same type, which are connected to each other using pointers. Array supports  Random Access , which means elements can be accessed directly using their index, like  arr[0]  for 1st element,  arr[6]  for 7th element etc. Hence, accessing elements in an array is  fast  with a constant time complexity of  O(1) . Linked List supports  Sequential Access , which means to access any element/node in a linked list, we have to
Read more

What is a Queue Data Structure?

-
Image
What is a Queue Data Structure? Queue  is also an abstract data type or a linear data structure, just like stack data structure, in which the first element is inserted from one end called the  REAR (also called  tail ), and the removal of existing element takes place from the other end called as  FRONT (also called  head ). This makes queue as  FIFO (First in First Out) data structure, which means that element inserted first will be removed first. Which is exactly how queue system works in real world. If you go to a ticket counter to buy movie tickets, and are first in the queue, then you will be the first one to get the tickets. Right? Same is the case with Queue data structure. Data inserted first, will leave the queue first. The process to add an element into queue is called  Enqueue  and the process of removal of an element from queue is called  Dequeue . Basic features of Queue Like stack, queue is also an ordered list of elements of similar data types. Queue is
Read more

Tree Traversal Techniques

-
Image
Traversal  is the method of processing each and every node in the Binary Search Tree exactly once in a systematic manner. There are three different types of tree traversal. (1) Preorder Traversal  (2) In order Traversal  (3) Post order Traversal PreOrder Traversal Steps for Preorder Traversal: (1) Process the root node first. (2) Traverse the left sub tree in preorder. (3) Traverse the right sub tree in preorder. InOrder Traversal Steps for Inorder Traversal: (1) Traverse the left sub tree in inorder. (2) Process the root node. (3) Traverse the right sub tree in inorder. PostOrder Traversal Steps for PostOrder Traversal: (1) Traverse the left sub tree in Post order. (2) Traverse the right sub tree in Post order. (3) Process the root node. Now Consider Following Example PreOrder Traversal :  A B D E C F G  InOrder Traversal :  D B E A F C G PostOrder Traversal :  D E B F G C A
Read more