Is linked list a linear data structure

Linked List Data Structure

• Last Updated : 01 Feb, 2022
  Table of Contents Show

  • Linked List Data Structure
  • Linear vs Non-Linear data structure
  • What is Data structure?
  • What is the Linear data structure?
  • What is a Non-linear data structure?
  • Differences between the Linear data structure and non-linear data structure.
  • Data structure — LinkedList

Practice Problems on Linked List
Recent Articles on Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Topics :

• Singly Linked List
• Circular Linked List
• Doubly Linked List

• Misc
• Quick Links

Singly Linked List :

1. Introduction to Linked List
2. Linked List vs Array
3. Linked List Insertion
4. Linked List Deletion (Deleting a given key)
5. Linked List Deletion (Deleting a key at given position)
6. Write a function to delete a Linked List
7. Find Length of a Linked List (Iterative and Recursive)
8. Search an element in a Linked List (Iterative and Recursive)
9. Write a function to get Nth node in a Linked List
10. Nth node from the end of a Linked List
11. Print the middle of a given linked list
12. Write a function that counts the number of times a given int occurs in a Linked List
13. Detect loop in a linked list
14. Find length of loop in linked list
15. Function to check if a singly linked list is palindrome
16. Remove duplicates from a sorted linked list
17. Remove duplicates from an unsorted linked list
18. Swap nodes in a linked list without swapping data
19. Pairwise swap elements of a given linked list
20. Move last element to front of a given Linked List
21. Intersection of two Sorted Linked Lists
22. Intersection point of two Linked Lists.
23. QuickSort on Singly Linked List
24. Segregate even and odd nodes in a Linked List
25. Reverse a linked list

More >>

Circular Linked List :

1. Circular Linked List Introduction and Applications,
2. Circular Linked List Traversal
3. Split a Circular Linked List into two halves
4. Sorted insert for circular linked list
5. Check if a linked list is Circular Linked List
6. Convert a Binary Tree to a Circular Doubly Link List
7. Circular Singly Linked List | Insertion
8. Deletion from a Circular Linked List
9. Circular Queue | Set 2 (Circular Linked List Implementation)
10. Count nodes in Circular linked list
11. Josephus Circle using circular linked list
12. Convert singly linked list into circular linked list
13. Circular Linked List | Set 1 (Introduction and Applications)
14. Circular Linked List | Set 2 (Traversal)
15. Implementation of Deque using circular array
16. Exchange first and last nodes in Circular Linked List

More >>

Doubly Linked List :

1. Doubly Linked List Introduction and Insertion
2. Delete a node in a Doubly Linked List
3. Reverse a Doubly Linked List
4. The Great Tree-List Recursion Problem.
5. Copy a linked list with next and arbit pointer
6. QuickSort on Doubly Linked List
7. Swap Kth node from beginning with Kth node from end in a Linked List
8. Merge Sort for Doubly Linked List
9. Create a Doubly Linked List from a Ternary Tree
10. Find pairs with given sum in doubly linked list
11. Insert value in sorted way in a sorted doubly linked list
12. Delete a Doubly Linked List node at a given position
13. Count triplets in a sorted doubly linked list whose sum is equal to a given value x
14. Remove duplicates from a sorted doubly linked list
15. Delete all occurrences of a given key in a doubly linked list
16. Remove duplicates from an unsorted doubly linked list
17. Sort the biotonic doubly linked list
18. Sort a k sorted doubly linked list
19. Convert a given Binary Tree to Doubly Linked List | Set
20. Program to find size of Doubly Linked List
21. Sorted insert in a doubly linked list with head and tail pointers
22. Large number arithmetic using doubly linked list
23. Rotate Doubly linked list by N nodes
24. Priority Queue using doubly linked list
25. Reverse a doubly linked list in groups of given size
26. Doubly Circular Linked List | Set 1 (Introduction and Insertion)
27. Doubly Circular Linked List | Set 2 (Deletion)

More >>

Misc :

1. Skip List | Set 1 (Introduction)
2. Skip List | Set 2 (Insertion)
3. Skip List | Set 3 (Searching and Deletion)
4. Reverse a stack without using extra space in O(n)
5. An interesting method to print reverse of a linked list
6. Linked List representation of Disjoint Set Data Structures
7. Sublist Search (Search a linked list in another list)
8. How to insert elements in C++ STL List ?
9. Unrolled Linked List | Set 1 (Introduction)
10. A Programmer’s approach of looking at Array vs. Linked List
11. How to write C functions that modify head pointer of a Linked List?
12. Given a linked list which is sorted, how will you insert in sorted way
13. Can we reverse a linked list in less than O(n)?
14. Practice questions for Linked List and Recursion
15. Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes
16. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
17. Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
18. Squareroot(n)-th node in a Linked List
19. Find the fractional (or n/k – th) node in linked list
20. Find modular node in a linked list
21. Construct a linked list from 2D matrix
22. Find smallest and largest elements in singly linked list
23. Arrange consonants and vowels nodes in a linked list
24. Partitioning a linked list around a given value and If we don’t care about making the elements of the list “stable”
25. Modify contents of Linked List

Quick Links :

• ‘Practice Problems’ on Linked List
• ‘Videos’ on Linked List
• ‘Quizzes’ on Linked List

If you still need more assistance with your placement preparation, have a look at our Complete Interview Preparation Course. The course has been designed by our expert mentors to help students crack the coding interview of top product or service-based organizations . You get access to premium lectures, 200+ coding questions bank, resume building tips, and lifetime access to the course content. So to make sure that your next programming interview doesn’t feel like an interrogation, enroll in Complete Interview Preparation and give a boost to your placement preparation.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Linear vs Non-Linear data structure

What is Data structure?

A data structure is a technique of storing and organizing the data in such a way that the data can be utilized in an efficient manner. In computer science, a data structure is designed in such a way that it can work with various algorithms. A data structure is classified into two categories:

• Linear data structure
• Non-linear data structure

Now let's have a brief look at both these data structures.

What is the Linear data structure?

A linear data structure is a structure in which the elements are stored sequentially, and the elements are connected to the previous and the next element. As the elements are stored sequentially, so they can be traversed or accessed in a single run. The implementation of linear data structures is easier as the elements are sequentially organized in memory. The data elements in an array are traversed one after another and can access only one element at a time.

The types of linear data structures are Array, Queue, Stack, Linked List.

Let's discuss each linear data structure in detail.

• Array: An array consists of data elements of a same data type. For example, if we want to store the roll numbers of 10 students, so instead of creating 10 integer type variables, we will create an array having size 10. Therefore, we can say that an array saves a lot of memory and reduces the length of the code.
• Stack: It is linear data structure that uses the LIFO (Last In-First Out) rule in which the data added last will be removed first. The addition of data element in a stack is known as a push operation, and the deletion of data element form the list is known as pop operation.
• Queue: It is a data structure that uses the FIFO rule (First In-First Out). In this rule, the element which is added first will be removed first. There are two terms used in the queue front end and rear The insertion operation performed at the back end is known ad enqueue, and the deletion operation performed at the front end is known as dequeue.
• Linked list: It is a collection of nodes that are made up of two parts, i.e., data element and reference to the next node in the sequence.

What is a Non-linear data structure?

A non-linear data structure is also another type of data structure in which the data elements are not arranged in a contiguous manner. As the arrangement is nonsequential, so the data elements cannot be traversed or accessed in a single run. In the case of linear data structure, element is connected to two elements (previous and the next element), whereas, in the non-linear data structure, an element can be connected to more than two elements.

Trees and Graphs are the types of non-linear data structure.

Let's discuss both the data structures in detail.

• Tree

It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent-child relationship. The diagrammatic representation of a tree data structure is shown below:

For example, the posts of employees are arranged in a tree data structure like managers, officers, clerk. In the above figure, A represents a manager, B and C represent the officers, and other nodes represent the clerks.

• Graph

A graph is a non-linear data structure that has a finite number of vertices and edges, and these edges are used to connect the vertices. The vertices are used to store the data elements, while the edges represent the relationship between the vertices. A graph is used in various real-world problems like telephone networks, circuit networks, social networks like LinkedIn, Facebook. In the case of facebook, a single user can be considered as a node, and the connection of a user with others is known as edges.

Differences between the Linear data structure and non-linear data structure.

Next TopicArray vs Linked List

← prev next →

Data structure — LinkedList

In the previous blog, we discussed arrays one of the most commonly known linear data structure in the programming world. Despite its simplicity and popularity Array by nature got few limitations,

• Arrays are static by nature which makes it less flexible to fit when the amount of data grows or shrinks
• Arrays are quite costly for common operations like insertion and deletion

In this blog, we are going to discuss another linear data structure called LinkedList which help to overcome a few limitations.