Doubly Linked List Algorithm

The Doubly Linked List Node Algorithm is a data structure that allows for the efficient manipulation and organization of elements in a dynamic list. Each node in a doubly linked list contains three components: the data element itself, a reference to the previous node in the list, and a reference to the next node in the list. This bidirectional linking of nodes enables traversal and modification of the list in both directions, which provides greater flexibility and functionality in comparison to its simpler counterpart, the singly linked list. In the Doubly Linked List Node Algorithm, insertion and deletion operations can be performed easily, without needing to traverse the entire list, as long as the target node is known. To insert a new node, the algorithm simply updates the pointers of the adjacent nodes, creating a connection between the new node and its neighbors. Similarly, to delete a node, the algorithm modifies the pointers of the neighboring nodes to bypass the target node, effectively removing it from the list. Despite the benefits of bidirectional traversal and improved manipulation capabilities, doubly linked lists do incur a slight overhead in terms of memory usage, as each node requires storage for two pointers rather than one. However, this trade-off is often deemed acceptable in applications where frequent modifications and versatile traversal capabilities are essential.
// Hamza chabchoub contribution for a university project
function DoubleLinkedList () {
  const Node = function (element) {
    this.element = element
    this.next = null
    this.prev = null
  }

  let length = 0
  let head = null
  let tail = null

  // Add new element
  this.append = function (element) {
    const node = new Node(element)

    if (!head) {
      head = node
      tail = node
    } else {
      node.prev = tail
      tail.next = node
      tail = node
    }

    length++
  }

  // Add element
  this.insert = function (position, element) {
    // Check of out-of-bound values
    if (position >= 0 && position <= length) {
      const node = new Node(element)
      let current = head
      let previous = 0
      let index = 0

      if (position === 0) {
        if (!head) {
          head = node
          tail = node
        } else {
          node.next = current
          current.prev = node
          head = node
        }
      } else if (position === length) {
        current = tail
        current.next = node
        node.prev = current
        tail = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        node.next = current
        previous.next = node

        // New
        current.prev = node
        node.prev = previous
      }

      length++
      return true
    } else {
      return false
    }
  }

  // Remove element at any position
  this.removeAt = function (position) {
    // look for out-of-bounds value
    if (position > -1 && position < length) {
      let current = head
      let previous = 0
      let index = 0

      // Removing first item
      if (position === 0) {
        head = current.next

        // if there is only one item, update tail //NEW
        if (length === 1) {
          tail = null
        } else {
          head.prev = null
        }
      } else if (position === length - 1) {
        current = tail
        tail = current.prev
        tail.next = null
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }

        // link previous with current's next - skip it
        previous.next = current.next
        current.next.prev = previous
      }

      length--
      return current.element
    } else {
      return null
    }
  }

  // Get the indexOf item
  this.indexOf = function (elm) {
    let current = head
    let index = -1

    // If element found then return its position
    while (current) {
      if (elm === current.element) {
        return ++index
      }

      index++
      current = current.next
    }

    // Else return -1
    return -1
  }

  // Find the item in the list
  this.isPresent = (elm) => {
    return this.indexOf(elm) !== -1
  }

  // Delete an item from the list
  this.delete = (elm) => {
    return this.removeAt(this.indexOf(elm))
  }

  // Delete first item from the list
  this.deleteHead = function () {
    this.removeAt(0)
  }

  // Delete last item from the list
  this.deleteTail = function () {
    this.removeAt(length - 1)
  }

  // Print item of the string
  this.toString = function () {
    let current = head
    let string = ''

    while (current) {
      string += current.element + (current.next ? '\n' : '')
      current = current.next
    }

    return string
  }

  // Convert list to array
  this.toArray = function () {
    const arr = []
    let current = head

    while (current) {
      arr.push(current.element)
      current = current.next
    }

    return arr
  }

  // Check if list is empty
  this.isEmpty = function () {
    return length === 0
  }

  // Get the size of the list
  this.size = function () {
    return length
  }

  // Get the head
  this.getHead = function () {
    return head
  }

  // Get the tail
  this.getTail = function () {
    return tail
  }
}

const newDoubleLinkedList = new DoubleLinkedList()
newDoubleLinkedList.append(1)
newDoubleLinkedList.append(2)
console.log('Testing: ' + newDoubleLinkedList.size()) // returns 2

LANGUAGE:

DARK MODE: