Computer Science/Data Structure
Linear and Nonlinear Data Structures(In progress)
JTB
2025. 9. 2. 06:34
Linear Data Structures
A linear data structure is a structure where elements are arranged in a sequential order.
Examples: Linked List, Array, Vector, Stack, Queue.
1) Linked List
A structure where nodes containing data are connected via pointers, maximizing space efficiency.
- Insertion/Deletion: O(1)
- Search/Access: O(n)
| Operation | Time Complexity | Notes |
| Lookup | O(n) | Must traverse from head |
| Assign | O(n) | Same reason |
| Find | O(n) | Same reason |
| Insert | O(1) | Adjust pointers |
| Remove (head/tail) | O(1) | |
| Remove (middle) | O(n) | Need to find previous node |
2) Array
An array is a collection of elements of the same type, stored in contiguous memory, with fixed size.
- Allows duplicates and maintains order.
- Best for frequent lookups.
| Operation | Time Complexity | Notes |
| Lookup(position) | O(1) | Direct indexing |
| Assign | O(1) | Direct indexing |
| Insert | O(n) | Elements must shift |
| Remove | O(n) | Elements must shift |
| Find(value) | O(n) | Linear search |
3) Vector
A dynamic array — resizable, random access, ordered, allows duplicates.
- Back insert/delete: O(1) (amortized)
- Middle insert/delete: O(n)
4) Stack
Follows LIFO (Last In First Out).
Used in recursion, algorithms, browser history, etc.
| Operation | Time Complexity |
| Insert (push) | O(1) |
| Remove (pop) | O(1) |
| Lookup/find | O(n) |
5) Queue
Follows FIFO (First In First Out) — opposite of stack.
Used in task scheduling, printers, etc.
| Operation | Time Complexity |
| Insert (enqueue) | O(1) |
| Remove (dequeue) | O(1) |
| Lookup/find | O(n) |