Linked List is an important topic belonging to the famous chapter of Computer Science i.e. Data Structure. And, when it comes to a competitive examination like GATE, you have to read the whole topic quite deeply. In this article, we have covered all the topics relevant to the linked list. We hope the notes for the CSE topics will help you understand this topic in a better way.
- What Is A Linked List?
- Types Of Linked List
- Basic Operations In Linked List
- Advantages Of Linked List
- Disadvantages Of Linked List
- Video on Linked List Problems
- Practice Problems – Linked List
- FAQs Related To Linked List
What is a Linked List?
A linked list is a sequence of data structures. It is also known as a linear data structure that comprises a set of connected nodes. Each node is used to store the data and also the address of the next node.
Explanation of Picture
- The starting point of the linked list is known as the head of the list. It is not a different node, but refers to the first node.
- The node present in the end is called NULL.
Types of Linked List
There are 3 different types of Linked Lists:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
1. Single Linked List
It is the most manageable type of linked list in which every node includes some data and the address part, which means a pointer to the next node in the series. In a singly linked list, we can perform operations like insertion, deletion, and traversal.
2. Doubly Linked List
When a node holds a data part and two addresses, it is known as a doubly-linked list. Two addresses means a pointer to the previous node and the next node.
3. Circular Linked List
In a circular linked list, the last node of the series contains the address of the first node to make a circular chain.
Basic Operations In Linked List
When it comes to linked lists, there are five operations supported by the series or list.
- Traversal – Through this operation, we can access elements.
- Insertion – In this operation, elements can be added at the starting of the list.
- Deletion – In this operation, elements can be deleted at the starting of the list.
- Search – Through this operation, we can easily search for an element utilising the provided key.
- Sort – Through this operation, we can sort the nodes of the linked list.
Advantages of Linked Lists
- A linked list is dynamic, which means it will provide memory whenever needed.
- In a linked list, we can swiftly execute the operations like insertion and deletion.
- We can easily implement stacks and queues.
- It helps in reducing the access time.
Disadvantages of Linked Lists
- Sometimes the memory gets wasted because pointers need extra memory for storage.
- We can access elements in sequence. You cannot do this process in a random manner.
- In a linked list, reverse traversing is challenging.
Video on Linked List Problems
Practice Problems – Linked List
Q. In a circular linked list organization, insertion of a record involves modification of:
- One Pointer
- One Pointer
- Multiple pointer
- No pointer
Q. Consider the function f defined below.
struct item {
int data;
struct item * next;
};
int f(struct item *p) {
return ((p == NULL) || (p ->next == NULL) ||
((p->data <= p -> next -> data) &&
f(p-> next)));
}
For a given linked list p, the function f returns 1 if and only if
- the list is empty or has exactly one element
- the elements in the list are sorted in non-decreasing order of data value
- the elements in the list are sorted in non-increasing order of data value
- not all elements in the list have the same data value
FAQs Related to Linked List
Is a linked list difficult?
Not as such. In a linked list, we can easily manage the insertion and deletion operation. The only difficult part is to access the element, or we can say that the access time is linear.
Which operations are supported by a linked list?
Insertion, deletion, search, traversal and sort.
What is a linked list?
A linked list is a set of nodes where each node is linked to the next node with the help of a pointer.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
- Introduction to Data structures
- Introduction to Array Notes
- Binary Heaps Notes
- Heap Sort Notes
- Binary Search Trees Notes
- AVL Trees Notes
- Graphs and their Applications
- Trees
- Stacks and their Applications
- Queues Notes
- Introduction to Recursion
- Difference between Singly Linked List and Doubly Linked List
- Difference between Array and Linked List
Comments