A linear list is a basic data structure consisting of a finite sequence of n (n ≥ 0) elements of the same type. The data elements in a linear list have a one-to-one linear relationship, meaning that except for the first and last elements, each element has a unique predecessor and successor.
Definition of Linear Lists
A linear list (List) is a finite sequence of data elements with the same characteristics, where:
- n is the length of the linear list (n ≥ 0)
- When n=0, it represents an empty list
- If n>0, the first element is called the head and has no predecessor
- If n>0, the last element is called the tail and has no successor
- Other elements have exactly one predecessor and one successor
Classification of Linear Lists
Linear lists can be divided into:
- Sequential Storage Structure: Uses a group of storage units with consecutive addresses to store the data elements of the linear list sequentially
- Array implementation
- Linked Storage Structure: Uses a group of arbitrary storage units to store the data elements of the linear list
- Singly linked list
- Doubly linked list
- Circular linked list
Sequential Storage Structure Implementation (Array Implementation)
Basic Implementation
class ArrayList {
constructor(capacity = 10) {
this.data = new Array(capacity);
this.length = 0;
this.capacity = capacity;
}
// Get element
get(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
return this.data[index];
}
// Set element
set(index, value) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
this.data[index] = value;
}
// Add element at the end
append(value) {
if (this.length === this.capacity) {
this.resize();
}
this.data[this.length] = value;
this.length++;
}
// Insert element at specified position
insert(index, value) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (this.length === this.capacity) {
this.resize();
}
// Move elements from index onwards one position back
for (let i = this.length; i > index; i--) {
this.data[i] = this.data[i - 1];
}
this.data[index] = value;
this.length++;
}
// Remove element at specified position
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
const removed = this.data[index];
// Move elements after index one position forward
for (let i = index; i < this.length - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.data[this.length - 1] = undefined; // Clear reference
this.length--;
return removed;
}
// Remove the first matching element
removeValue(value) {
const index = this.indexOf(value);
if (index !== -1) {
return this.remove(index);
}
return undefined;
}
// Find the index of an element
indexOf(value) {
for (let i = 0; i < this.length; i++) {
if (this.data[i] === value) {
return i;
}
}
return -1;
}
// Check if contains an element
contains(value) {
return this.indexOf(value) !== -1;
}
// Clear the linear list
clear() {
this.data = new Array(this.capacity);
this.length = 0;
}
// Resize capacity
resize() {
const newCapacity = this.capacity * 2;
const newData = new Array(newCapacity);
for (let i = 0; i < this.length; i++) {
newData[i] = this.data[i];
}
this.data = newData;
this.capacity = newCapacity;
}
// Get the size of the linear list
size() {
return this.length;
}
// Check if empty
isEmpty() {
return this.length === 0;
}
// Convert to array
toArray() {
return this.data.slice(0, this.length);
}
}
Time Complexity Analysis
| Operation | Time Complexity |
|---|---|
| get | O(1) |
| set | O(1) |
| append | Average O(1), Worst O(n) (when resizing) |
| insert | O(n) |
| remove | O(n) |
| indexOf/removeValue | O(n) |
| contains | O(n) |
| size/isEmpty | O(1) |
Linked Storage Structure Implementation
Singly Linked List Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Add node at the end
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}
// Add node at the beginning
prepend(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
if (!this.tail) {
this.tail = newNode;
}
this.length++;
}
// Insert node at specified position
insert(index, data) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (index === 0) {
this.prepend(data);
return;
}
if (index === this.length) {
this.append(data);
return;
}
const newNode = new Node(data);
const leader = this.getNodeAt(index - 1);
newNode.next = leader.next;
leader.next = newNode;
this.length++;
}
// Get node at specified position
getNodeAt(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
let currentNode = this.head;
let counter = 0;
while (counter < index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
// Get element
get(index) {
const node = this.getNodeAt(index);
return node.data;
}
// Set element
set(index, data) {
const node = this.getNodeAt(index);
node.data = data;
}
// Remove node at specified position
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
if (index === 0) {
const removedNode = this.head;
this.head = this.head.next;
if (this.length === 1) {
this.tail = null;
}
this.length--;
return removedNode.data;
}
const leader = this.getNodeAt(index - 1);
const removedNode = leader.next;
leader.next = removedNode.next;
if (index === this.length - 1) {
this.tail = leader;
}
this.length--;
return removedNode.data;
}
// Remove the first matching element
removeValue(value) {
let current = this.head;
let previous = null;
while (current) {
if (current.data === value) {
if (previous === null) {
this.head = current.next;
if (this.length === 1) {
this.tail = null;
}
} else {
previous.next = current.next;
if (current.next === null) {
this.tail = previous;
}
}
this.length--;
return current.data;
}
previous = current;
current = current.next;
}
return undefined;
}
// Find the index of an element
indexOf(value) {
let current = this.head;
let index = 0;
while (current) {
if (current.data === value) {
return index;
}
current = current.next;
index++;
}
return -1;
}
// Check if contains an element
contains(value) {
return this.indexOf(value) !== -1;
}
// Clear the list
clear() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Get the size of the list
size() {
return this.length;
}
// Check if empty
isEmpty() {
return this.length === 0;
}
// Convert to array
toArray() {
const array = [];
let current = this.head;
while (current) {
array.push(current.data);
current = current.next;
}
return array;
}
}
Doubly Linked List Implementation
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Add node at the end
append(data) {
const newNode = new DoublyNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
}
// Add node at the beginning
prepend(data) {
const newNode = new DoublyNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length++;
}
// Insert node at specified position
insert(index, data) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (index === 0) {
this.prepend(data);
return;
}
if (index === this.length) {
this.append(data);
return;
}
const newNode = new DoublyNode(data);
const leader = this.getNodeAt(index - 1);
const follower = leader.next;
leader.next = newNode;
newNode.prev = leader;
newNode.next = follower;
follower.prev = newNode;
this.length++;
}
// Get node at specified position
getNodeAt(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
let current;
if (index < this.length / 2) {
// From head
current = this.head;
let counter = 0;
while (counter < index) {
current = current.next;
counter++;
}
} else {
// From tail
current = this.tail;
let counter = this.length - 1;
while (counter > index) {
current = current.prev;
counter--;
}
}
return current;
}
// Get element
get(index) {
const node = this.getNodeAt(index);
return node.data;
}
// Set element
set(index, data) {
const node = this.getNodeAt(index);
node.data = data;
}
// Remove node at specified position
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
let removedNode;
if (index === 0) {
removedNode = this.head;
this.head = this.head.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null;
}
} else if (index === this.length - 1) {
removedNode = this.tail;
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null;
}
} else {
removedNode = this.getNodeAt(index);
removedNode.prev.next = removedNode.next;
removedNode.next.prev = removedNode.prev;
}
this.length--;
return removedNode.data;
}
// Remove the first matching element
removeValue(value) {
let current = this.head;
while (current) {
if (current.data === value) {
if (current.prev) {
current.prev.next = current.next;
} else {
this.head = current.next;
}
if (current.next) {
current.next.prev = current.prev;
} else {
this.tail = current.prev;
}
this.length--;
return current.data;
}
current = current.next;
}
return undefined;
}
// Find the index of an element
indexOf(value) {
let current = this.head;
let index = 0;
while (current) {
if (current.data === value) {
return index;
}
current = current.next;
index++;
}
return -1;
}
// Check if contains an element
contains(value) {
return this.indexOf(value) !== -1;
}
// Clear the list
clear() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Get the size of the list
size() {
return this.length;
}
// Check if empty
isEmpty() {
return this.length === 0;
}
// Convert to array
toArray() {
const array = [];
let current = this.head;
while (current) {
array.push(current.data);
current = current.next;
}
return array;
}
}
Circular Linked List Implementation
class CircularLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Add node at the end
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
newNode.next = this.head; // Point to itself
} else {
newNode.next = this.head; // New node points to head
this.tail.next = newNode; // Original tail points to new node
this.tail = newNode; // Update tail
}
this.length++;
}
// Add node at the beginning
prepend(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
newNode.next = this.head;
} else {
newNode.next = this.head;
this.tail.next = newNode;
this.head = newNode;
}
this.length++;
}
// Insert node at specified position
insert(index, data) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (index === 0) {
this.prepend(data);
return;
}
if (index === this.length) {
this.append(data);
return;
}
const newNode = new Node(data);
const leader = this.getNodeAt(index - 1);
newNode.next = leader.next;
leader.next = newNode;
this.length++;
}
// Get node at specified position
getNodeAt(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
let current = this.head;
let counter = 0;
while (counter < index) {
current = current.next;
counter++;
}
return current;
}
// Get element
get(index) {
const node = this.getNodeAt(index);
return node.data;
}
// Set element
set(index, data) {
const node = this.getNodeAt(index);
node.data = data;
}
// Remove node at specified position
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error('Index out of bounds');
}
if (this.length === 1) {
const removedData = this.head.data;
this.head = null;
this.tail = null;
this.length--;
return removedData;
}
if (index === 0) {
const removedData = this.head.data;
this.tail.next = this.head.next;
this.head = this.head.next;
this.length--;
return removedData;
}
const leader = this.getNodeAt(index - 1);
const removedData = leader.next.data;
leader.next = leader.next.next;
if (index === this.length - 1) {
this.tail = leader;
}
this.length--;
return removedData;
}
// Remove the first matching element
removeValue(value) {
if (!this.head) {
return undefined;
}
if (this.head.data === value) {
return this.remove(0);
}
let current = this.head;
let previous = null;
do {
previous = current;
current = current.next;
if (current.data === value) {
previous.next = current.next;
if (current === this.tail) {
this.tail = previous;
}
this.length--;
return current.data;
}
} while (current !== this.head);
return undefined;
}
// Find the index of an element
indexOf(value) {
if (!this.head) {
return -1;
}
let current = this.head;
let index = 0;
do {
if (current.data === value) {
return index;
}
current = current.next;
index++;
} while (current !== this.head);
return -1;
}
// Check if contains an element
contains(value) {
return this.indexOf(value) !== -1;
}
// Clear the list
clear() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Get the size of the list
size() {
return this.length;
}
// Check if empty
isEmpty() {
return this.length === 0;
}
// Convert to array
toArray() {
if (!this.head) {
return [];
}
const array = [];
let current = this.head;
do {
array.push(current.data);
current = current.next;
} while (current !== this.head);
return array;
}
// Print the list
print() {
console.log(this.toArray().join(' <-> '));
}
}
Applications of Linear Lists
Stack Implementation (Based on Array)
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}
Queue Implementation (Based on Linked List)
class Queue {
constructor() {
this.items = new DoublyLinkedList();
}
enqueue(element) {
this.items.append(element);
}
dequeue() {
return this.items.removeHead();
}
front() {
return this.items.get(0);
}
isEmpty() {
return this.items.isEmpty();
}
size() {
return this.items.size();
}
clear() {
this.items.clear();
}
}
Josephus Problem
function josephus(n, m) {
const circularList = new CircularLinkedList();
// Initialize circular linked list
for (let i = 1; i <= n; i++) {
circularList.append(i);
}
let currentNode = circularList.head;
let previousNode = null;
let count = 0;
// While there is more than one node in the list
while (circularList.size() > 1) {
count++;
// Find the m-th node
if (count === m) {
// Remove current node
if (previousNode) {
previousNode.next = currentNode.next;
} else {
// If removing the head node
circularList.head = currentNode.next;
}
// If the tail node is removed
if (currentNode.next === circularList.head) {
circularList.tail = previousNode;
}
circularList.length--;
count = 0;
currentNode = currentNode.next;
} else {
previousNode = currentNode;
currentNode = currentNode.next;
}
}
return circularList.head.data;
}
console.log(josephus(7, 3)); // Output the survivor's position
Polynomial Addition
class Polynomial {
constructor() {
this.terms = new DoublyLinkedList();
}
addTerm(coefficient, exponent) {
this.terms.append({ coefficient, exponent });
}
add(polynomial) {
const result = new Polynomial();
let p1 = this.terms.head;
let p2 = polynomial.terms.head;
while (p1 && p2) {
if (p1.data.exponent > p2.data.exponent) {
result.addTerm(p1.data.coefficient, p1.data.exponent);
p1 = p1.next;
} else if (p1.data.exponent < p2.data.exponent) {
result.addTerm(p2.data.coefficient, p2.data.exponent);
p2 = p2.next;
} else {
const sum = p1.data.coefficient + p2.data.coefficient;
if (sum !== 0) {
result.addTerm(sum, p1.data.exponent);
}
p1 = p1.next;
p2 = p2.next;
}
}
// Add remaining terms
while (p1) {
result.addTerm(p1.data.coefficient, p1.data.exponent);
p1 = p1.next;
}
while (p2) {
result.addTerm(p2.data.coefficient, p2.data.exponent);
p2 = p2.next;
}
return result;
}
toString() {
let str = '';
let current = this.terms.head;
while (current) {
const { coefficient, exponent } = current.data;
if (str) {
str += ' + ';
}
str += `${coefficient}x^${exponent}`;
current = current.next;
}
return str;
}
}
const p1 = new Polynomial();
p1.addTerm(3, 2);
p1.addTerm(4, 1);
p1.addTerm(5, 0);
const p2 = new Polynomial();
p2.addTerm(2, 2);
p2.addTerm(-4, 1);
p2.addTerm(1, 0);
const sum = p1.add(p2);
console.log(sum.toString()); // Output: 5x^2 + 6x^0
Performance Comparison of Linear Lists
| Operation | Sequential Storage (Array) | Linked Storage (Singly Linked List) | Linked Storage (Doubly Linked List) |
|---|---|---|---|
| Access Element | O(1) | O(n) | O(n) |
| Insert/Delete at Head | O(n) (requires shifting elements) | O(1) | O(1) |
| Insert/Delete at Tail | O(1) (if capacity is known) | O(1) | O(1) |
| Insert/Delete in Middle | O(n) (requires shifting elements) | O(n) (requires traversal) | O(n) (requires traversal) |
| Memory Usage | Contiguous memory, may waste space | Dynamic allocation, no waste | Dynamic allocation, no waste |
| Implementation Complexity | Simple | Medium | More complex |
Summary
Linear lists are one of the most basic data structures, providing a foundation for other complex data structures (such as stacks, queues, trees, etc.). Depending on different application scenarios and performance requirements, sequential storage (array) or linked storage (singly linked list/doubly linked list) can be chosen to implement linear lists.
- Sequential Storage is suitable for scenarios with frequent access but less insertion/deletion
- Linked Storage is suitable for scenarios with frequent insertion/deletion but less random access
- Doubly Linked List is more efficient than singly linked list when frequent operations at head and tail are needed
Understanding the implementation principles and performance characteristics of linear lists is very important for solving practical problems, especially when optimizing data structure performance.
