Skip to content

Latest commit

 

History

History

doubly-linked-list

README.md

Doubly Linked Lists 🍀

Objectives

  1. Construct a Doubly Linked List
  2. Compare and contrast Doubly and Singly Linked Lists
  3. Implement basic operations on a Doubly Linked List

1. What is a doubly linked list?

  • Almost identical to Singly Linked Lists, except every node has another pointer, to the previous node!

    Doubly linked list

  • Check out Visualgo.net, click DLL to see the visualization.

2. Comparisons with Singly Linked Lists

  • More memory === More Flexibility
  • It's almost always a tradeoff!

3. Class diagram

Doubly linked list Class diagram

4. Big O

Doubly linked list BigO

5. Recap ⛱

  • Doubly Linked Lists are almost identical to Singly Linked Lists except there is an additional pointer to previous nodes.
  • Better than Singly Linked Lists for finding nodes and can be done in half the time!
  • However, they do take up more memory considering the extra pointer.
  • Doubly linked lists are used to implement other data structures and certain types of caches

👈 Back to Data Structures dir

References