| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 10,000 push & pop | 212.98 | 4.70 | 0.01 |
| 10,000 insertBefore | 250.68 | 3.99 | 0.01 |
Singly Linked List
npm install singly-linked-list-typed!NPM
!GitHub top language
!npm
!eslint
!npm bundle size
!npm bundle size
!npm
This is a standalone Singly Linked List data structure from the data-structure-typed collection. If you wish to access
more data structures or advanced features, you can transition to directly installing the
complete data-structure-typed package
``bash`
npm i singly-linked-list-typed --save
`bash`
yarn add singly-linked-list-typed
[//]: # (No deletion!!! Start of Example Replace Section)
typescript
// Create a simple SinglyLinkedList with initial values
const list = new SinglyLinkedList([1, 2, 3, 4, 5]); // Verify the list maintains insertion order
console.log([...list]); // [1, 2, 3, 4, 5];
// Check length
console.log(list.length); // 5;
// Push a new element to the end
list.push(6);
console.log(list.length); // 6;
console.log([...list]); // [1, 2, 3, 4, 5, 6];
`$3
`typescript
const list = new SinglyLinkedList([10, 20, 30, 40, 50]); // Pop removes from the end
const last = list.pop();
console.log(last); // 50;
// Shift removes from the beginning
const first = list.shift();
console.log(first); // 10;
// Verify remaining elements
console.log([...list]); // [20, 30, 40];
console.log(list.length); // 3;
`$3
`typescript
const list = new SinglyLinkedList([20, 30, 40]); // Unshift adds to the beginning
list.unshift(10);
console.log([...list]); // [10, 20, 30, 40];
// Access elements (forward traversal only for singly linked)
const second = list.at(1);
console.log(second); // 20;
// SinglyLinkedList allows forward iteration only
const elements: number[] = [];
for (const item of list) {
elements.push(item);
}
console.log(elements); // [10, 20, 30, 40];
console.log(list.length); // 4;
`$3
`typescript
const list = new SinglyLinkedList([1, 2, 3, 4, 5]); // Filter even numbers
const filtered = list.filter(value => value % 2 === 0);
console.log(filtered.length); // 2;
// Map to double values
const doubled = list.map(value => value * 2);
console.log(doubled.length); // 5;
// Use reduce to sum
const sum = list.reduce((acc, value) => acc + value, 0);
console.log(sum); // 15;
`$3
`typescript
interface LogEntry {
timestamp: number;
level: 'INFO' | 'WARN' | 'ERROR';
message: string;
} // SinglyLinkedList is ideal for sequential processing where you only need forward iteration
// O(1) insertion/deletion at head, O(n) for tail operations
const logStream = new SinglyLinkedList();
// Simulate incoming log entries
const entries: LogEntry[] = [
{ timestamp: 1000, level: 'INFO', message: 'Server started' },
{ timestamp: 1100, level: 'WARN', message: 'Memory usage high' },
{ timestamp: 1200, level: 'ERROR', message: 'Connection failed' },
{ timestamp: 1300, level: 'INFO', message: 'Connection restored' }
];
// Add entries to the stream
for (const entry of entries) {
logStream.push(entry);
}
console.log(logStream.length); // 4;
// Process logs sequentially (only forward iteration needed)
const processedLogs: string[] = [];
for (const log of logStream) {
processedLogs.push(
[${log.level}] ${log.message});
} console.log(processedLogs); // [
// '[INFO] Server started',
// '[WARN] Memory usage high',
// '[ERROR] Connection failed',
// '[INFO] Connection restored'
// ];
// Get first log (O(1) - direct head access)
const firstLog = logStream.at(0);
console.log(firstLog?.message); // 'Server started';
// Remove oldest log (O(1) operation at head)
const removed = logStream.shift();
console.log(removed?.message); // 'Server started';
console.log(logStream.length); // 3;
// Remaining logs still maintain order for sequential processing
console.log(logStream.length); // 3;
`$3
`typescript
class TextEditor {
private content: SinglyLinkedList;
private cursorIndex: number;
private undoStack: Stack<{ operation: string; data?: any }>; constructor() {
this.content = new SinglyLinkedList();
this.cursorIndex = 0; // Cursor starts at the beginning
this.undoStack = new Stack<{ operation: string; data?: any }>(); // Stack to keep track of operations for undo
}
insert(char: string) {
this.content.addAt(this.cursorIndex, char);
this.cursorIndex++;
this.undoStack.push({ operation: 'insert', data: { index: this.cursorIndex - 1 } });
}
delete() {
if (this.cursorIndex === 0) return; // Nothing to delete
const deleted = this.content.deleteAt(this.cursorIndex - 1);
this.cursorIndex--;
this.undoStack.push({ operation: 'delete', data: { index: this.cursorIndex, char: deleted } });
}
moveCursor(index: number) {
this.cursorIndex = Math.max(0, Math.min(index, this.content.length));
}
undo() {
if (this.undoStack.size === 0) return; // No operations to undo
const lastAction = this.undoStack.pop();
if (lastAction!.operation === 'insert') {
this.content.deleteAt(lastAction!.data.index);
this.cursorIndex = lastAction!.data.index;
} else if (lastAction!.operation === 'delete') {
this.content.addAt(lastAction!.data.index, lastAction!.data.char);
this.cursorIndex = lastAction!.data.index + 1;
}
}
getText(): string {
return [...this.content].join('');
}
}
// Example Usage
const editor = new TextEditor();
editor.insert('H');
editor.insert('e');
editor.insert('l');
editor.insert('l');
editor.insert('o');
console.log(editor.getText()); // 'Hello'; // Output: "Hello"
editor.delete();
console.log(editor.getText()); // 'Hell'; // Output: "Hell"
editor.undo();
console.log(editor.getText()); // 'Hello'; // Output: "Hello"
editor.moveCursor(1);
editor.insert('a');
console.log(editor.getText()); // 'Haello';
``[//]: # (No deletion!!! End of Example Replace Section)
| Data Structure | Unit Test | Performance Test | API Docs |
|---|---|---|---|
| Singly Linked List | SinglyLinkedList |
| Data Structure Typed | C++ STL | java.util | Python collections |
|---|---|---|---|
| SinglyLinkedList<E> | - | - | - |
[//]: # (No deletion!!! Start of Replace Section)
| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 10,000 push & pop | 212.98 | 4.70 | 0.01 |
| 10,000 insertBefore | 250.68 | 3.99 | 0.01 |
[//]: # (No deletion!!! End of Replace Section)
| Algorithm | Function Description | Iteration Type |
|---|
| Principle | Description |
|---|---|
| Practicality | Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names. |
| Extensibility | Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures. |
| Modularization | Includes data structure modularization and independent NPM packages. |
| Efficiency | All methods provide time and space complexity, comparable to native JS performance. |
| Maintainability | Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns. |
| Testability | Automated and customized unit testing, performance testing, and integration testing. |
| Portability | Plans for porting to Java, Python, and C++, currently achieved to 80%. |
| Reusability | Fully decoupled, minimized side effects, and adheres to OOP. |
| Security | Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects. |
| Scalability | Data structure software does not involve load issues. |