CS133 - Data Structures and File Organizations - Flashcards

Vocabulary flashcards for reviewing linked lists concepts.

Linked List

A dynamic data structure consisting of a sequence of nodes, where each node contains data and a link (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, providing flexibility in terms of memory usage and insertion/deletion operations.

Linked Structure

A general term referring to any data structure that uses links or pointers to connect elements (nodes). This structure allows for non-contiguous memory allocation and dynamic resizing, making it suitable for various applications where data size is not known in advance or changes frequently.

Node

A basic building block of a linked list, comprising two main parts: data, which stores the actual information, and a pointer (or link), which holds the address of the next node in the sequence. In doubly linked lists, a node also contains a pointer to the previous node.

Singly Linked List

A type of linked list in which each node contains data and a single pointer to the next node in the sequence. Traversal is unidirectional, from the head (first node) to the tail (last node). Insertion and deletion operations are efficient at the beginning of the list but can be slower at the end.

Doubly Linked List

An advanced type of linked list where each node contains data and two pointers: one to the next node and one to the previous node. This bidirectional linking allows for traversal in both forward and backward directions, enhancing the efficiency of certain operations like reverse traversal and deletion of a node given its address.

Circular Linked List

A variation of a linked list where the last node (tail) points back to the first node (head), forming a closed loop. This structure eliminates the need for null pointers to indicate the end of the list and can simplify certain algorithms, such as those used in round-robin scheduling.

appendNode()

A function or method used to add a new node containing specified data to the end of a linked list. This operation typically involves traversing the list to find the last node and then updating its 'next' pointer to point to the new node.

displayNodes()

A function that iterates through a linked list from the head to the tail, displaying the data contained in each node. This is a fundamental operation for visualizing the contents of the list and verifying the correctness of other operations.

displayNodesReverse()

A function that displays the contents of a linked list in reverse order, starting from the last node and moving towards the first. This can be implemented using recursion or by first reversing the list and then displaying it.

destroyList()

A function responsible for deallocating the memory occupied by the nodes of a linked list. This prevents memory leaks by ensuring that all nodes are removed from memory when the list is no longer needed. The list itself still exists, but will become empty of Nodes.