Solution: Doubly linked list - Go教程

(upbeat music) - [Instructor] Review your solution as you have a look at my implementation of the Add function of the doubly linked list. There are four base cases to consider. Adding to an empty list. Adding an element to the head of the list. Adding an element to the tail of the list. And finally, adding an element at a given index. The code begins by saving the current size of the list to a variable. As always, our error case comes first. On lines 31 to 33, the code checks whether the index exceeds the size of the list and returns an error if it does. Once the error case is handled, we know we'll add the element to the list. On lines 34 to 37, we create an element with the given value and increment the size of the linked list. As there is no underlying array that contains the elements of the linked list, it's best to manage the size of the list manually. On lines 40 to 43, handle the case of the empty list by checking that the list is empty by verifying whether its head field is nil. In this case, we set both the head and tail of the list to the new element. Next, on lines 46 to 50, handle the case where the index is zero, changing the head of the list. The case of the empty list has been handled already, so you can set the head of the list as the new element's next. Then assign the new element as the old list head node previous value and assign the new element to the list head. Because we're implementing a doubly linked list, we need to handle both references to the previous and next nodes. Following the same process, we handle the case of changing the tail of the list on lines 53 to 57. In this case, we set the tail as the new element's previous node then set the new element to the tail node's next. Finally, set the new element as the list's tail node. The last case we need to handle is appending a node to the middle of the list. Linked lists are not accessed by index, so you need to find the correct node to append after by looping from the head of the list. Do this by using the for range on lines 60 to 63. In order for this element to take place at the given index, stop the iteration before the given index. Once you found the correct element, begin to manipulate the references of the surrounding nodes. The new element takes the current node as its previous value, and the next value of the current node becomes the next value of the new element. The references of the current node values are changed to the new element as well supporting traversal in both directions. That's all the code required for implementing our generic doubly linked list. Run the code using the Test my code button. The output is what we expected. You've successfully implemented our first data structuring goal and completed the challenge. Congratulations.