Linear data structure
A linear list in data structures is a sequence of elements in which each element has a unique predecessor and a unique successor, except for the first and last elements. This type of data structure organizes elements in a linear or sequential manner, meaning that data items are arranged one after another.
Types of Linear Lists:
1. Array:
A collection of elements stored in contiguous memory locations.
Fixed size.
Direct access to elements via index.
2. Linked List:
A collection of nodes where each node contains data and a reference (or link) to the next node.
Dynamic size, as memory is allocated when required.
Types of Linked Lists:
▪ Singly Linked List: Each node points to the next node.
▪ Doubly Linked List: Each node has two pointers, one to the next node and one to the previous node.
▪ Circular Linked List: The last node points to the first node.
3. Stack:
A list that follows the Last-In-First-Out (LIFO) principle.
Operations are performed at one end, called the "top" of the stack.
Used for undo operations, expression evaluation, and backtracking.
4. Queue:
A list that follows the First-In-First-Out (FIFO) principle.
Elements are added at the rear and removed from the front.
Used in scheduling algorithms, breadth-first search, etc.
Characteristics of Linear Lists:
• Order: Elements are ordered sequentially.
• Traversal: Can be traversed one element after another.
• Memory: Arrays use contiguous memory, while linked lists use non-contiguous memory.
• Insertion and Deletion: Easier in linked lists (dynamic resizing), more complex in arrays due to fixed size.
Linked Representation of Linear Lists:
A linear list (also known as a sequence or an array) can be represented in data structures using a linked list. A linked list is a dynamic data structure that consists of nodes, where each node contains two parts:
1. Data: The value stored in the node.
2. Pointer (Link): A reference (or link) to the next node in the sequence.
In the linked list representation, each element in the list is stored in a node, and the link or pointer connects the nodes.
Array Representation of linear list:
A linear list (or simply a list) is a data structure in which elements are arranged in a linear sequence, where each element has a unique successor, except for the last one. The array representation of a linear list refers to storing this sequence of elements in an array, where each element is stored in consecutive memory locations.
Key Features of Array Representation:
1. Contiguous Memory: Elements are stored in contiguous memory locations.
2. Index-based Access: Elements can be accessed directly by their index in constant t ime, i.e., O(1)
3. Fixed Size: Arrays have a predefined size, meaning the number of elements in the array is fixed and cannot dynamically grow without creating a new array and copying the elements.
4. Efficient Access, but Costly Insertion/Deletion:
Accessing any element is very fast due to direct indexing.
Inserting or deleting elements can be costly since elements may need to be shifted to maintain the order of the list.
Example:
Consider a linear list of numbers: L = [10, 20, 30, 40]. In an array representation, it would look like this in memory:
Index 0 1 2 3
Value 10 20 30 40
• To access the element 30, you simply use the index 2: L[2] = 30.
• If you want to insert 25 between 20 and 30, you need to shift elements 30 and 40 to the right, making it less efficient.
In summary, a linear list in an array representation is an efficient way to store and access a sequence of elements when the size is known in advance, and random access is needed frequently. However, insertions and deletions are costly due to shifting elements.
Data Objects and Structures in Linear List Data Structure
In the context of a linear list, data objects and structures refer to the elements and organizational methods used to store and manage the elements in a sequential manner. The main linear data structures include arrays, linked lists, stacks, and queues. Here's an overview of the data objects and data structures in these linear lists:
1. Data Objects in a Linear List
A data object refers to a value or a set of values that can be stored in a data structure. These objects are typically the elements (or nodes) that are stored in a linear list. Each data object may consist of:
• Primitive data types: These include basic data types like integers, characters, floats, and booleans.
• Composite data types: These include more complex data types, such as strings, arrays, or user-defined data types like structures or objects.
For example:
• In an array of integers: the data objects are individual integer values.
• In a linked list: the data objects are nodes containing data and a reference to the next node.
2. Data Structures in a Linear List
Data structures organize and store data objects in a way that enables efficient access and modification. Linear data structures store elements sequentially, where each element (except the first and last) has a unique predecessor and a unique successor. Here are the key linear data structures and how they manage data objects:
a. Arrays
An array is a data structure that stores a collection of elements of the same type, arranged in contiguous memory locations.
• Data Object: A single element at each index (e.g., int, float, etc.).
• Structure: Fixed-size, contiguous memory locations where each element is indexed.
• Access: Constant-time access (O(1)) using an index.
Example:
int arr[5] = {1, 2, 3, 4, 5};
Index 0 1 2 3 4
Value 1 2 3 4 5
b. Linked Lists
A linked list is a dynamic data structure made up of nodes, where each node contains data and a pointer (or reference) to the next node in the sequence.
• Data Object: The data part of each node (can be any type).
• Structure: A collection of nodes, where each node has two parts: data and a reference to the next node.
• Access: Sequential access, where traversal starts at the head node and moves through links (O(n) for searching).
c. Stack
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element added is the first one to be removed.
• Data Object: The element (data) at the top of the stack.
• Structure: A collection of elements, where operations like insertion and deletion are performed at one end (the top).
• Access: You can only access the element at the top (O(1) for push and pop operations).
d. Queue
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first element added is the first one to be removed.
• Data Object: The elements stored in the queue, where the element at the front is the next one to be removed.
• Structure: A collection of elements, where insertion is done at the rear (enqueue), and removal is done from the front (dequeue).
• Access: Only the element at the front can be dequeued, while new elements are added at the rear (O(1) for both enqueue and dequeue operations).
3. Operations on Linear Lists
In all linear data structures, the following operations are common:
• Insertion: Adding an element to the list (can vary based on the type of structure). • Deletion: Removing an element from the list.
• Traversal: Accessing and processing each element in the list.
• Searching: Finding a specific element in the list.
• Updating: Modifying the data of an element in the list.
The efficiency of these operations varies based on the type of linear structure. For example, arrays allow constant-time access (O(1)), while linked lists allow for dynamic resizing but have O(n) search time.
Summary of Data Objects and Structures in Linear Lists
• Data objects in linear lists are the individual elements stored in the structure (such as integers, floats, or complex objects).
• Data structures in linear lists include:
Arrays (fixed-size, contiguous memory),
Linked Lists (dynamic, with nodes pointing to the next element),
Stacks (LIFO structure), o Queues (FIFO structure).
Each of these structures has specific use cases and performance characteristics depending on the needs of the application.
Linear List Representation in Arrays and Vectors
Both arrays and vectors are used to represent linear lists, but they differ in terms of memory allocation, flexibility, and internal implementation. Below is a comparison between arrays and vectors in the context of data structures:
1. Array Representation
An array is a collection of elements stored in contiguous memory locations. It is a fixed-size data structure, meaning the size is defined when the array is created and cannot be altered dynamically.
Key Characteristics of Arrays:
• Fixed size: The number of elements is defined during array creation and cannot be changed at runtime.
• Indexing: Elements are accessed using an index, and access time is constant (O(1)).
• Contiguous memory: All elements are stored sequentially in memory, which enhances performance but limits flexibility.
• Inflexible resizing: If the array is full, a new larger array has to be created and elements copied over.
Example of Array Representation:
int arr[5] = {10, 20, 30, 40, 50};
In memory, this looks like:
Index Value
0 10
1 20
2 30
3 40
4 50
Advantages of Arrays:
• Constant-time access: You can access any element in O(1) time using its index.
• Efficient for static data: If the number of elements is known in advance, arrays are very efficient.
Disadvantages of Arrays:
• Fixed size: Cannot grow or shrink once created, leading to potential wastage of memory or overflow.
• Costly insertions and deletions: Adding or removing elements, especially in the middle, requires shifting other elements.
2. Vector Representation (Dynamic Array)
A vector (in C++, std::vector, or similar dynamic arrays in other languages) is a dynamic array that can grow and shrink as needed. Unlike arrays, vectors manage their own memory and can resize automatically.
Key Characteristics of Vectors:
• Dynamic size: Vectors can grow or shrink dynamically, resizing as needed.
• Automatic resizing: When a vector's capacity is full, it creates a new, larger array (often double the size) and copies the elements to the new memory space.
• Contiguous memory: Like arrays, vectors store elements contiguously, ensuring constant-time access to elements.
• Amortized insertion: Although resizing might take O(n) during expansion, on average, insertions take constant time (O(1)) due to amortized allocation.
Example of Vector Representation (C++ STL Vector):
#include
std::vector vec = {10, 20, 30, 40, 50};
vec.push_back(60); // Adds 60 to the vector, resizes if needed
In memory, after the push:
Index Value
0 10
1 20
2 30
3 40
4 50
5 60
Advantages of Vectors:
• Dynamic resizing: Automatically adjusts the size, so you don’t have to worry about overflow.
• Efficient insertions and deletions: Elements can be added or removed easily, especially at the end.
• STL (Standard Template Library) support: In languages like C++, vectors are part of the STL, making them versatile and easy to use.
Disadvantages of Vectors:
• Resizing overhead: When the vector needs to resize, it reallocates memory and copies all elements, which can be costly.
• Extra memory allocation: Vectors often allocate more memory than required to reduce the need for frequent resizing, which can lead to slight memory inefficiencies.
When to Use Arrays vs Vectors:
• Arrays: Useful when you know the number of elements in advance and won’t need to add or remove elements frequently.
• Vectors: Ideal when the number of elements is not fixed, and you expect to frequently modify the size of the list.