Doubly Linked List

Linked List/Queue/Stack Pending –
1. circular
2. round petrol problem
3. linked list and stack and queue mixed problem
4. cracking the coding interview problem
5. InterviewBit Problem Set

Make it a point to maintain a tail node in DLL and a size variable.

  1. ** Doubly Linked List

  2. **Reverse Doubly Linked List   Code

  3. *** Sort a linked list of 0,1 and 2’s –  count 0, 1 and 2’s.
    Algo:
    –  We can count the number of nodes having 0,1,2 and then make a new list with equal number of nodes.
    –  We can do it on O(n) with no extra space. Code. The way this code works is without interchanging data and linking up nodes. It creates there node, one each for 0,1 and 2. Then start traversing the list. Depending on the data of the node we link the current node to the specific node – either 0/1/2.  This logic can be used for singly linked list as well as we don’t rely on traversing from in the opposite direction.
    –  The third logic is same as used for sorting an array of 0,1 and 2. Since we can traverse backwards in the DDL, we will use that to our use.
    Dutch national flag sorting problemSort an array of 0s, 1s and 2s.
    (1) Create a low pointer at the beginning of the array and a high pointer at the end of the array.
    (2) Create a mid pointer that starts at the beginning of the array and iterates through each element.
    (3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the high pointer by 1.
    (4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the low and mid pointers by 1.
    (5) If the element at arr[mid] is a 1, don’t swap anything and just increase the mid pointer by 1.


  4. ** Swap Kth node from beginning with Kth node from end in a Singly Linked List –
    GFG. Algo –
    Let X be the kth node from beginning and Y be the kth node from end.
    Following are the interesting cases that must be handled.
    1) Y is next to X
    2) X is next to Y
    3) X and Y are same
    4) X and Y don’t exist (k is more than number of nodes in linked list)


  5. *** Design a stack with operations on middle element.
    How to implement a stack which will support following operations in O(1) time complexity? Link
    1) push() which adds an element to the top of stack.
    2) pop() which removes an element from top of stack.
    3) findMiddle() which will return middle element of the stack.
    4) deleteMiddle() which will delete the middle element.
    Implementing a stack using a Singly Linked List is pretty straightforward.  So what we do is to maintain a middlePointer(ok, that’s obvious) and have a flag which indicates when to move the middle pointer. We move the middle pointer when there was an element addition and the total node count became odd.
    When the list is empty middlePointer points to the first element. Now when the 3 node is added the middlePointer should be moved to it’s next.
    When an element is poped we may have to readjust the middlePointer. If there was even number of element, after pop it becomes odd, so now the middle needs to be moved back by one node. Since we need to move back to maintain the middlePointer in O(1) we will use a double linked list.
    C Code here is pretty clean


Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s