- Define a doubly linked list data structure
- Implement a common methods of a doubly linked list class
Today we'll be implementing a doubly linked list. A doubly linked list is
like a singly-linked list, except it has an extra attribute on each node: a
prev
pointer that points to the previous node.
For this challenge, assume that only one node is added at a time, including upon initialization of a new list.
Each node should have a pointer called prev
that points to the node that comes
before it. If no node comes before it, it should be a falsy value, such as
null
in JS or nil
in Ruby.
node = new Node('first')
node.prev
=> nil or null
node.prev = new Node('zeroth')
node.prev
=> Node with value 'zeroth'
Look through the methods and determine which need to be modified in order to
ensure that a node's prev
attribute always points to the correct Node.
list = new LinkedList
list.add_first(new Node('zeroth'))
list.head
=> Node with value 'zeroth'
list.head.prev
=> nil or null
list.add_first(new Node('less than zero'))
list.head
=> Node with value 'less than zero'
list.head.next
=> Node with value 'zeroth'
list.head.next.prev
=> Node with value 'less than zero'
list.remove_first
list.head
=> Node with value 'zeroth'
list.head.prev
=> nil or null
Use the language of your choosing. We've included code from the original
LinkedList
implementation. You may also copy and paste your own.
We've also included the original LinkedList
tests, so you can ensure that your
code still functions correctly.
- Rewrite the problem in your own words
- Validate that you understand the problem
- Write your own test cases
- Pseudocode
- Code!
And remember, don't run our tests until you've passed your own!
cd
into the ruby folderruby <filename>.rb
cd
into the javascript foldernode <filename>.js
cd
into the ruby folderbundle install
rspec
cd
into the javascript foldernpm i
npm test