Hadron DaVinci

Find Value at Middle Node in Double Linked List

15 Aug 2020 - Hadron DaVinci

Problem

Find Middle Node of Double Linked List:
1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6

Discussion

Truths:

1. A linked list is not the same data structure as an array or list.
   • so we can’t just jump to the middle index.
   • we can only get there by accessing a node which points to it
2. A double linked list means that one can traverse the linked list forwards and backwards.
   Specifically, each node has a reference to the next and previous node.
   
   

Solutions

Method1 (Brute Force):

step1:

Obtain the length of linked list by iterating from left side to right side once
while counting the number of nodes.

• Let length_linked_list = number of nodes

step2:

Find the mid point.

• Let mid_point = length_linked_list/2

step3:

Iterate through the list until we get to the middle

• Let current_node_index = 0, as code iterates, do current_node_index += 1
  Stop when current_node_index >= mid_point

Method2 (Meet in Middle):

Since it’s a double linked list, we can iterate from both the left and right side.

step1:

Iterate from left side and right side at the same time.

step2:

When both iterators are on the same node, then it would be in the middle.

How would the code tell when the two are on the same node, you may ask?
Simply by comparing something unique about each node which may be either
the pointer, the node itself, the memory address that the node occupies in ram, etc.