Linked List Notes For GATE

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?

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:

  1. Singly Linked List
  2. Doubly Linked List
  3. 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.

Practice Problems – Linked List

Q. In a circular linked list organization, insertion of a record involves modification of:

  1. One Pointer
  2. One Pointer
  3. Multiple pointer
  4. 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

  1. the list is empty or has exactly one element
  2. the elements in the list are sorted in non-decreasing order of data value
  3. the elements in the list are sorted in non-increasing order of data value
  4. not all elements in the list have the same data value


Keep learning and stay tuned to get the latest updates on GATE Exam along with Eligibility Criteria, GATE Syllabus for CSE (Computer Science Engineering)GATE CSE NotesGATE CSE Question Paper, and more.

Keep learning and stay tuned to get the latest updates on <a href=”https://byjus.com/gate/gate-exam/”>GATE Exam</a> along with <a href=”https://byjus.com/gate/gate-eligibility-criteria/”>GATE Eligibility Criteria</a>, <a href=”https://byjus.com/gate/”>GATE 2023</a>, <a href=”https://byjus.com/gate/gate-admit-card/”>GATE Admit Card</a>, <a href=”https://byjus.com/gate/gate-syllabus-for-computer-science-engineering/”>GATE Syllabus for CSE (Computer Science Engineering)</a>, <a href=”https://byjus.com/gate/gate-notes-for-cse/”>GATE CSE Notes</a>, <a href=”https://byjus.com/gate/gate-cse-question-paper/”>GATE CSE Question Paper</a>, and more.

Also Explore,

Leave a Comment

Your Mobile number and Email id will not be published.

*

*