Add Doubly Linked List Node in Singly Linked List

Question

Given singly Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null
Modify middle element as doubly Linked List Node
here middle element is 3
3 -> next should point to 4
3 -> prev should point to 1

Can any one suggest how can it be done ? interviewer gave me hint use interface. but I couldn't figure it out how.
I have to iterate over this linked list and print all the node and when it reaches to the middle, print where next and prev is pointing to, then print till the end of the list.
Expected output : 1, 2, Middle: 3, Prev: 1, Next: 4, 5

I'm facing problem in adding the middle node.

Answer 1

By definition, a single-linked list consists of single-linked nodes only, and a double-linked consists of double-linked nodes only. Otherwise. it is neither.

By definition the field prev of a double-linked list must point to the previous element.

Whatever you are supposed to build. It's something not well specified. So if you really were asked this in an interview (and did not misunderstand the question - maybe he wanted you to point out that ghis violates the interface?) this is a case for the code horror stories of http://thedailywtf.com/ - section "incompetent interviewers".

Answer 2

So, this "works", but if this is expected to be answered on an interview, it is way too much work.

LinkedList

public class LinkedList {

    public interface Linkable<V, L extends Linkable> {
        V getValue();
        L getNext();
        void setNext(L link);
    }

    public static class Node implements Linkable<Integer, Linkable> {
        int value;
        Linkable next;

        Node(int value) {
            this.value = value;
        }

        @Override
        public Integer getValue() {
            return value;
        }

        @Override
        public Linkable getNext() {
            return next;
        }

        @Override
        public void setNext(Linkable link) {
            this.next = link;
        }
    }

    private Linkable head;

    public boolean isEmpty() {
        return this.head == null;
    }

    public Linkable getHead() {
        return head;
    }

    public void add(int v) {
        Node next = new Node(v);
        if (isEmpty()) {
            this.head = next;
        } else {
            Linkable tmp = this.head;
            while (tmp.getNext() != null) {
                tmp = tmp.getNext();
            }
            tmp.setNext(next);
        }
    }
}

---

Interface

interface DoublyLinkable<V, L extends LinkedList.Linkable> extends LinkedList.Linkable<V,L> {
    LinkedList.Linkable getPrev();
    void setPrev(LinkedList.Linkable prev);
}

DoubleNode

public class DoubleNode extends LinkedList.Node implements DoublyLinkable<Integer, LinkedList.Linkable> {
    LinkedList.Linkable prev;

    public DoubleNode(int value) {
        super(value);
    }

    @Override
    public LinkedList.Linkable getPrev() {
        return prev;
    }

    @Override
    public void setPrev(LinkedList.Linkable prev) {
         this.prev = prev;
    }
}

---

Driver

Outputs

1, 2, Middle: 3, Prev: 1, Next: 4, 5

---

public class Driver {

    public static LinkedList getList() {
        LinkedList list = new LinkedList();
        for (int i = 1; i <= 5; i++) {
            list.add(i);
        }
        return list;
    }

    public static void main(String[] args) {

        LinkedList list = getList();

        LinkedList.Linkable head = list.getHead();
        LinkedList.Linkable beforeMiddle = null;
        LinkedList.Linkable middle = list.getHead();
        LinkedList.Linkable end = list.getHead();

        if (head != null) {
            // find the middle of the list
            while (true) {
                if (end.getNext() == null || end.getNext().getNext() == null) break;

                beforeMiddle = middle;
                middle = middle.getNext();

                end = end.getNext().getNext();
            }

            // Replace middle by reassigning the pointer to it
            if (beforeMiddle != null) {

                DoubleNode n = new DoubleNode((int) middle.getValue()); // same value
                n.setPrev(list.getHead()); // point back to the front
                n.setNext(middle.getNext()); // point forward to original value

                beforeMiddle.setNext((DoublyLinkable) n);
                middle = beforeMiddle.getNext();
            }

            // Build the "expected" output
            StringBuilder sb = new StringBuilder();
            final String DELIMITER = ", ";
            head = list.getHead();
            boolean atMiddle = false;
            if (head != null) {
                do {
                    if (head instanceof DoublyLinkable) {
                        atMiddle = true;
                        String out = String.format("Middle: %d, Prev: %d, ", (int) head.getValue(), (int) ((DoublyLinkable) head).getPrev().getValue());
                        sb.append(out);
                    } else {
                        if (atMiddle) {
                            sb.append("Next: ");
                            atMiddle = false;
                        }
                        sb.append(head.getValue()).append(DELIMITER);
                    }

                    head = head.getNext();
                } while (head != null);
            }
            sb.setLength(sb.length() - DELIMITER.length());

            System.out.println(sb.toString());
        }

    }
}

Answer 3

If you haven't, you'd better define a lenght() function so given one linked list you can know how many nodes does it have.

Thanks to the response of Cereal_Killer to the previous version of this answer, I noticed that the list is firstly a singly linked list, and you just have to make the middle node be linked both to the next node and to some previous node.

Now I guess that you have defined two structures (Struct, Class or whatever depending on the language you're using). So lets say you have Node_s defined as a node with only a next pointer, and Node_d with both a next and a prev pointer. (Node_d may inherite from Node_s so you just have to add the prev attribute in the child class). Knowing this, the code above should be doing what you need:

function do_it(my_LinkedList linkedList){

    int i_middle;
    int length = linkedList.length();

    if ( (length ÷ 2 ) != 0 ) i_middle = length / 2;
    else return -1; 

    Node_s aux = linkedList.first();
    int index = 0;
    Node_d middle= null;

    while (aux != null) {

       if (index == i_middle - 1){ //now aux is the middle's previous node

            middle.data = aux.next.data; //aux.next is the middle singly node, we assignate the data to the new double linked node

            middle.prev = aux; //as we said, aux is the prev to the middle
            midle.next = aux.next.next; //so aux.next.next is the next to the middle
            print(what you need to print);
       }else {
            print("Node " + index " next:  "+ aux.next);
       }//end if

       index++;
       aux = aux.next;
    } //end while

}//end function

This previous code should be doing what you need. I wrote the answer in some kind of pseudo-java code so if you're not familiar with Java or don't understand what my pseudo-code does, please let me know. Anyway, the idea of my code may present some troubles depending on the language you're working with, so you'll have to adapt it.

Note that at the end of the execution of this program, your data structure won't be a singly linked list, and neither a double one, since you'll have linkedList.length() - 1 nodes linked in a signly way but the middle one will have two links.

Hope this helps.