Linked Lists Vocabulary

Flashcards about Linked Lists

Linked List

A dynamic, linear data structure where elements (nodes) are not stored in contiguous memory locations. Each node contains a data field and a pointer (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.

Node

A fundamental unit of a linked list, consisting of two parts: a 'data' field, which stores the actual information, and a 'next' pointer, which holds the address of the subsequent node in the list. In the last node, this pointer typically points to 'null'.

Head Node

The first node in a linked list. It serves as the entry point to the list, and through it, all other nodes can be accessed. The head node does not necessarily contain data directly but points to the first data-containing node.

Tail Node

The last node in a linked list. It is identified by its 'next' pointer pointing to 'null', signifying the end of the list. Operations like appending to the list often involve updating the tail.

Singly Linked List

A type of linked list where each node contains a data field and a single 'next' pointer, which points to the next node in the list. Traversal is possible in only one direction—from the head towards the tail.

Doubly Linked List

An advanced type of linked list where each node contains a data field, a 'next' pointer (pointing to the next node), and a 'prev' pointer (pointing to the previous node). This structure allows for bidirectional traversal.

Circular Linked List

A linked list in which the tail node's 'next' pointer points back to the head node, creating a loop. This can be either a singly or doubly linked list. Useful in applications where you need to cycle through the list continuously.

Insertion

The process of adding a new node to a linked list. This can occur at the beginning (as the new head), at the end (as the new tail), or at a specified position within the list. The pointers of adjacent nodes need to be adjusted to maintain list integrity.

Deletion

The process of removing a node from a linked list. This can occur at the beginning, at the end, or at a specified position (or by specifying a key to locate the node). The pointers of adjacent nodes need to be adjusted to maintain list integrity.

Traversal

The act of visiting each node in a linked list, typically in sequential order, starting from the head. This is done to process, display, or search for specific data within the list.

Reversal Operation

An operation that rearranges the nodes in a linked list such that the order is inverted (i.e., the last node becomes the head, and the head becomes the last node). This involves modifying the 'next' pointers of each node.

Search Operation

The process of finding a specific element within a linked list by comparing each node's data field with a given key. The search continues until the element is found or the end of the list is reached.

Advantages of Linked Lists over Arrays

Linked lists offer dynamic size adjustment and efficient insertion/deletion of elements compared to arrays, which have a fixed size and require shifting elements upon insertion or deletion.

Disadvantages of Linked Lists compared to Arrays

Linked lists require more memory due to the storage of pointers, and they do not support random access. Accessing an element in a linked list requires traversal from the head, resulting in O(n) time complexity.

Time Complexity of Inserting at the Beginning of a Singly Linked List

The time complexity is O(1), assuming you have a reference to the head. The new node simply needs to be created and its 'next' pointer assigned to the current head.

Time Complexity of Searching in a Singly Linked List

The time complexity is O(n), where n is the number of nodes in the list. In the worst case, the target element is at the end of the list or not present, requiring a full traversal.