Doubly Linked List (DLL) Solution

In this assignment we are going to build on these ideas to create what is called a [doubly linked list](https://en.wikipedia.org/wiki/Doubly_linked_list) or a DLL




Reflection on the previous implementation.




What did you do to reset the head each time you dequed an element from the stack?




If the stack had n elements how many operations (i.e comparisisons ) did you have to do to reset the head?




How would you express this in big Oh notation.




What do you think you can do to make the dequeing constant time?




What are some operations that the stack doesn't provide that would proove desirable?




The pictures behind the code




You might have guessed about adding a previous field to our node that would point to the previous neighbor of a node. You guessed right. By doing this you would have created a [doubly linked list](https://en.wikipedia.org/wiki/Doubly_linked_list) or a DLL .




Lets try to visualize how our DLL would look like. To begin, our single linked list can be pictured like this:




<img src="./../images/SingleLinkedList.png"




Each node stores the data and a pointer to the next node.




Note that our stack looked almost exactly like our list:




<img src="./../images/Stack.png"




By adding a previous field to our node our list would like like this:




<img src="./../images/DoubleLinkedList.png"




Thus a node will know who comes before and after it.




Our new DLL struct




Remember that our stack linked the nodes for us when we enqueued an element? The stack did this by using a variable head which stores the position of where the next element needs to go. In our new DLL struct besides having a head pointer we are also going to add a tail pointer. head will point to the start of the DLL and the tail will point to the end of the DLL . This will enable us efficient adding and removing at both ends of the DLL .




```cpp

typedef struct DLL{

int count;

node_t head; // head points to the first node in our DLL.

node_t tail; // head points to the last node in our DLL.

}dll_t;

```




Part 1 - Implementing a Doubly Linked List (Your TO DO )




Implement the functions provided to you in the dd_list.h file. Do not modify the signatures ( names and arguments ) of these functions just provide the implementation (i.e. body of code).




Drawing a picture can help.




Note that drawing a picture of what needs to happen for each operation will help. For example:




push_front




<img src="./../images/push_back.png"




push_back




<img src="./../images/push_front.png"




insert(int index, int data)




<img src="./../images/insert.png"




Unit Tests




A unit test is a standalone test that checks for the correctness of a specific use case in your code. In our case, we are testing if we have a working DLL implementation.




Please write unit tests to test your implementation. Some example tests we might come up with include:




Fill a DLL , empty the DLL , and fill the DLL again.

Test each function in your DLL when the DLL is not empty.

Test each function in your DLL when the DLL is empty.

etc.




Rubric




- Part 1

- 50% Correct Doubly-Linked List(DLL) implementation

- All functions should be implemented. Do not rename the functions, but you may add any 'helper' functions if you deem necessary.

- (e.g. You might have a 'double_linked_list_print' to help you debug)

- There should be no memory leaks

- There should be no bugs in your functions

- Your implementation will be graded by our set of unit tests, and we will check your code 'style' as well.




Resources to help




- This is a nice interactive tutorial for learning C

- http://www.learn-c.org/

- Doubly Linked List Data Type High level description

- https://en.wikipedia.org/wiki/Doubly_linked_list (abstract_data_type)

 

Feedback Loop




(An optional task that will reinforce your learning throughout the semester)




- Investigate/Review more data strutures on this webpage: https://visualgo.net/en/list

- There are visuals for the doubly-linked list here!

- Use them as a rough outline for the general concept. Do make sure to follow the specifications above.