![NPM](https://img.shields.io/npm/l/doubly-linked-list-typed)
![GitHub top language](https://img.shields.io/github/languages/top/zrwusa/data-structure-typed)
![npm](https://img.shields.io/npm/dw/doubly-linked-list-typed)
![eslint](https://aleen42.github.io/badges/src/eslint.svg)
![npm bundle size](https://img.shields.io/bundlephobia/minzip/doubly-linked-list-typed)
![npm bundle size](https://img.shields.io/bundlephobia/min/doubly-linked-list-typed)
![npm](https://img.shields.io/npm/v/doubly-linked-list-typed)

# What

## Brief

This is a standalone Doubly 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](https://www.npmjs.com/package/data-structure-typed) package

# How

## install

### npm

```bash
npm i doubly-linked-list-typed --save
```

### yarn

```bash
yarn add doubly-linked-list-typed
```

### snippet

[//]: # (No deletion!!! Start of Example Replace Section)

### Browser history
```typescript
 const browserHistory = new DoublyLinkedList<string>();

    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';
```

### DoublyLinkedList for LRU cache implementation
```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<CacheEntry>();
    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';
```

### Find first matching element
```typescript
 const list = new DoublyLinkedList<number>([5, 10, 15, 20]);
    console.log(list.find(n => n >= 12)); // 15;
```

### Iterate over elements
```typescript
 const list = new DoublyLinkedList<number>([1, 2, 3]);
    const sum: number[] = [];
    list.forEach(n => sum.push(n));
    console.log(sum); // [1, 2, 3];
```

[//]: # (No deletion!!! End of Example Replace Section)


## API docs & Examples

[API Docs](https://data-structure-typed-docs.vercel.app)

[Live Examples](https://vivid-algorithm.vercel.app)

<a href="https://github.com/zrwusa/vivid-algorithm" target="_blank">Examples Repository</a>

## Data Structures

<table>
<thead>
<tr>
<th>Data Structure</th>
<th>Unit Test</th>
<th>Performance Test</th>
<th>API Docs</th>
</tr>
</thead>
<tbody>
<tr>
<td>Doubly Linked List</td>
<td><img src="https://raw.githubusercontent.com/zrwusa/assets/master/images/data-structure-typed/assets/tick.svg" alt=""></td>
<td><img src="https://raw.githubusercontent.com/zrwusa/assets/master/images/data-structure-typed/assets/tick.svg" alt=""></td>
<td><a href="https://data-structure-typed-docs.vercel.app/classes/DoublyLinkedList.html"><span>DoublyLinkedList</span></a></td>
</tr>
</tbody>
</table>

## Standard library data structure comparison

<table>
  <thead>
  <tr>
    <th>Data Structure Typed</th>
    <th>C++ STL</th>
    <th>java.util</th>
    <th>Python collections</th>
  </tr>
  </thead>
  <tbody>
  <tr>
    <td>DoublyLinkedList&lt;E&gt;</td>
    <td>list&lt;T&gt;</td>
    <td>LinkedList&lt;E&gt;</td>
    <td>-</td>
  </tr>
  </tbody>
</table>

## Benchmark

[//]: # (No deletion!!! Start of Replace Section)
<div class="json-to-html-collapse clearfix 0">
      <div class='collapsible level0' ><span class='json-to-html-label'>doubly-linked-list</span></div>
      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>221.57</td><td>4.51</td><td>0.03</td></tr><tr><td>1,000,000 unshift</td><td>229.02</td><td>4.37</td><td>0.07</td></tr><tr><td>1,000,000 unshift & shift</td><td>169.21</td><td>5.91</td><td>0.02</td></tr><tr><td>1,000,000 insertBefore</td><td>314.48</td><td>3.18</td><td>0.07</td></tr></table></div>
    </div>

[//]: # (No deletion!!! End of Replace Section)

## Built-in classic algorithms

<table>
  <thead>
  <tr>
    <th>Algorithm</th>
    <th>Function Description</th>
    <th>Iteration Type</th>
  </tr>
  </thead>
  <tbody>
 
  </tbody>
</table>

## Software Engineering Design Standards
<table>
    <tr>
        <th>Principle</th>
        <th>Description</th>
    </tr>
    <tr>
        <td>Practicality</td>
        <td>Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names.</td>
    </tr>
    <tr>
        <td>Extensibility</td>
        <td>Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures.</td>
    </tr>
    <tr>
        <td>Modularization</td>
        <td>Includes data structure modularization and independent NPM packages.</td>
    </tr>
    <tr>
        <td>Efficiency</td>
        <td>All methods provide time and space complexity, comparable to native JS performance.</td>
    </tr>
    <tr>
        <td>Maintainability</td>
        <td>Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns.</td>
    </tr>
    <tr>
        <td>Testability</td>
        <td>Automated and customized unit testing, performance testing, and integration testing.</td>
    </tr>
    <tr>
        <td>Portability</td>
        <td>Plans for porting to Java, Python, and C++, currently achieved to 80%.</td>
    </tr>
    <tr>
        <td>Reusability</td>
        <td>Fully decoupled, minimized side effects, and adheres to OOP.</td>
    </tr>
    <tr>
        <td>Security</td>
        <td>Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects.</td>
    </tr>
    <tr>
        <td>Scalability</td>
        <td>Data structure software does not involve load issues.</td>
    </tr>
</table>