[Array array] Continuous Space Storage and [Linked List linked list] Discrete Space Storage are two basic data structures, representing two different storage methods of data in computer memory, each exhibiting complementary characteristics.
Array array#
[Array array] is a linear data structure that stores elements of the same type in contiguous memory space. The length of an array is immutable.
Drawbacks of insertion and deletion: High time complexity O(n), element loss, memory wastage.
Typical applications: Random access, sorting and searching, lookup tables, machine learning, data structure implementation.
Linked List linked list#
[Linked List linked list] is a linear data structure where each element is a node object, and the nodes are connected through "references".
The reference stores the memory address of the next node. The design of a linked list allows nodes to be stored in memory in various locations.
Head node, tail node, tail node points to "null".
Linked lists occupy more memory space than arrays due to storing references.
// **Singly** linked list
// **Typical applications: stacks and queues, hash tables, graphs**
class ListNode {
int val;
ListNode? next;
ListNode(int x) => val = x;
}
// **Doubly** linked list
// **Typical applications (quickly finding previous/next elements): advanced data structures, browser history, LRU algorithm.**
class ListNode {
int val;
ListNode? next;
ListNode? prev;
ListNode(int x) => val = x;
}
// **Circular** linked list
// Similar to doubly linked list, except it is circular
// **Typical applications (periodic operations): time slice round-robin scheduling algorithm, data buffer.**
class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode(int x) => val = x;
}