Hello and welcome back! On my last post, I went over the operations used when working with singly-linked lists, namely append, prepend, lookup, insert, and delete, by building a simplified linked-list from scratch. I'm sure the whole time you read my last you were wondering if I was aware that I hadn't mentioned anything regarding a node's pointers. Well, I forgot. So here I am covering one of the characteristics that separates a singly linked list from the next sub-data structure I will cover: doubly-linked lists.
Pointers and Doubly Linked Lists
If the namesake isn't enough of a giveaway, pointers in a singly-linked list point towards a single direction, from head to tail. This does not mean that a linked list is sorted, like an array. It means that the node in question simply points to another node in a sequential, but not enumerated, order. This is why looking up a node in a linked list has linear time complexity O(n). Singly linked lists require traversal to access their values. If we look back at arrays, we see that iteration, an array's equivalent to the lookup operation, also runs in O(n) time. One thing that array lookup has over linked lists, is random access of the elements in the data structure. We can look up array elements by their indices, and return a value in O(1) time, but to look up a node in a linked list requires traversal, starting from the head node, down the linked list one-by-one, comparing values until we reach the target node. That's where pointers come in. Pointers are refs to the next node in a linked list. It points our search in a sequential order. However, we there is a way to include pointers in two directions. Doubly Linked Lists, in fact, contain such pointers. One group of pointers leading from the head node to the tail node, and another set pointing from the tail node to the head node. Unfortunately, all this does is increase the allocated memory due to the second set of pointers. What's more is that lookup remains with a time complexity of O(n), since we must traverse a linked list the same, regardless of the starting end.
I will keep this one brief, since the difference between doubly linked lists is pretty much splitting hairs. Traversal works the same way, plus a method for traversing from tail to head. Next time I will move on to the next data structure that is likely to be encountered during a technical interview: trees. Until next time!
Top comments (0)