| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 1,000,000 push | 221.57 | 4.51 | 0.03 |
| 1,000,000 unshift | 229.02 | 4.37 | 0.07 |
| 1,000,000 unshift & shift | 169.21 | 5.91 | 0.02 |
| 1,000,000 insertBefore | 314.48 | 3.18 | 0.07 |
Linked List
npm install linked-list-typed!NPM
!GitHub top language
!npm
!eslint
!npm bundle size
!npm bundle size
!npm
This is a standalone 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 linked-list-typed --save
`bash`
yarn add linked-list-typed
[//]: # (No deletion!!! Start of Example Replace Section)
typescript
// Create a simple DoublyLinkedList with initial values
const list = new DoublyLinkedList([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 DoublyLinkedList([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 DoublyLinkedList([1, 2, 3, 4, 5]); // Iterate through list
const doubled = list.map(value => value * 2);
console.log(doubled.length); // 5;
// Use for...of loop
const result: number[] = [];
for (const item of list) {
result.push(item);
}
console.log(result); // [1, 2, 3, 4, 5];
`$3
`typescript
const browserHistory = new DoublyLinkedList(); browserHistory.push('home page');
browserHistory.push('search page');
browserHistory.push('details page');
console.log(browserHistory.last); // 'details page';
console.log(browserHistory.pop()); // 'details page';
console.log(browserHistory.last); // 'search page';
`$3
`typescript
interface CacheEntry {
key: string;
value: string;
} // Simulate LRU cache using DoublyLinkedList
// DoublyLinkedList is perfect because:
// - O(1) delete from any position
// - O(1) push to end
// - Bidirectional traversal for LRU policy
const cacheList = new DoublyLinkedList();
const maxSize = 3;
// Add cache entries
cacheList.push({ key: 'user:1', value: 'Alice' });
cacheList.push({ key: 'user:2', value: 'Bob' });
cacheList.push({ key: 'user:3', value: 'Charlie' });
// Try to add a new entry when cache is full
if (cacheList.length >= maxSize) {
// Remove the oldest (first) entry
const evicted = cacheList.shift();
console.log(evicted?.key); // 'user:1';
}
// Add new entry
cacheList.push({ key: 'user:4', value: 'Diana' });
// Verify current cache state
console.log(cacheList.length); // 3;
const cachedKeys = [...cacheList].map(entry => entry.key);
console.log(cachedKeys); // ['user:2', 'user:3', 'user:4'];
// Access entry (in real LRU, this would move it to end)
const foundEntry = [...cacheList].find(entry => entry.key === 'user:2');
console.log(foundEntry?.value); // 'Bob';
``[//]: # (No deletion!!! End of Example Replace Section)
| Data Structure | Unit Test | Performance Test | API Docs |
|---|---|---|---|
| Linked List | SinglyLinkedList | ||
| Singly Linked List | SinglyLinkedList | ||
| Doubly Linked List | DoublyLinkedList |
| Data Structure Typed | C++ STL | java.util | Python collections |
|---|---|---|---|
| DoublyLinkedList<E> | list<T> | LinkedList<E> | - |
| SinglyLinkedList<E> | - | - | - |
[//]: # (No deletion!!! Start of Replace Section)
| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 1,000,000 push | 221.57 | 4.51 | 0.03 |
| 1,000,000 unshift | 229.02 | 4.37 | 0.07 |
| 1,000,000 unshift & shift | 169.21 | 5.91 | 0.02 |
| 1,000,000 insertBefore | 314.48 | 3.18 | 0.07 |
| 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. |