A linked list is a data structure used for storing collections of data. A linked list has the following properties.
- Successive elements are connected by pointers.
- Last element points to nil
- Can grow or shrink in size during execution of a program.
- Can be made just as long as required (until system memory is exhausted)
- It does not waste memory space, but takes a little extra because of pointers.
- push - adds an element to the end of the list.
- pop - removes the last element of the list and returns the data.
- delete - removes all elements of the list.
- count - returns the number of elements in the list.
- find(n) - returns the value of the nth node in the list.
- delete_at(n) - removes the node at the position n and returns its value.
- includes?(x) - returns true if a node contains the data x, returns false if it does not
- Also known as as a two-way linked list.
- Given a node in the list, we can navigate in both directions.
- A node knows about its next node, but also its previous node.
- In singly linked lists and doubly linked lists, the end of lists are nil.
- Circular linked lists do not have ends.
- While traversing the circular linked lists, we should be careful, or else we end up traversing the list infinitely.
- Start off by implementing a linked list.
- Be sure to write tests to verify your functionality.
- After you've got a linked list working with all of the main operations working, write the tests for and then implement a doubly linked list. This should be relatively trivial to do. delete_at(n) will require the most refactoring to make it function with a doubly linked list.
- You should not have to modify any tests, and you should not be breaking any older tests.
- When you've finished that, implement a circular linked list with the same guidelines as above. Be careful not to get yourself into an infinite loop!