Computer Science

Linear Data Structures

Linked Lists - Intermediate

     

Doubly linked lists are useful for more than just inserting and removing elements from the head and tail of the list. They can maintain a list of elements that allows for insertion and removal to the interior of the list

Given a node vv of a doubly linked list (which is currently followed by ww), we want to insert a new node zz immediately after vv. Concretely, we want to write a function insert(v) which takes a node, vv, and inserts a new node after vv. The result should be a list where vv's next points to zz, zz's next points to ww, ww's prev points to zz, and zz's prev points to vv.

If we execute these events in the wrong order, we can erase crucial information that will break the list. How should the following steps be ordered so that they correctly insert a node in-the middle of a doubly linked list?

  • A Make zz's prev point to vv.
  • B Make vv's next point to zz.
  • C Make ww's prev point to zz.
  • D Make zz's next point to ww.

Consider a circularly linked list. Which of the following methods below removes the node after the cursor? The cursor is a special node which allows us to have a place to start from if we ever need to traverse a circularly linked list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
node A(node N){
    Node oldNode = cursor.getNext();
    if (oldNode == cursor)
        cursor = node.getNext()
    else{
        cursor.setPrev(oldNode.getNext());
        oldNode.setNext(null);
    }
    size --;
    return oldNode;
}

1
2
3
4
5
node B(Node N){
    Node oldNode = N
    oldNode.setNext(null)
    return oldNode;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
node C(Node N){
    Node oldNode = cursor.getNext();
    if (oldNode == cursor)
        cursor = null
    else{
        cursor.setNext(oldNode.getNext());
        oldNode.setNext(null);
    }
    size --;
    return oldNode;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
node D(Node N){
    Node oldNode = N;
    if (oldNode == cursor)
        cursor = null
    else{
        cursor.setNext(N);
        oldNode.setNext(null);
    }
    size --;
    return oldNode;
}

Given a singly linked list, write a program the shifts every node kk unit to the left.

For example

When 4\rightarrow6\rightarrow8\rightarrow9 is shifted 22 units left it becomes 8\rightarrow9\rightarrow4\rightarrow6

What will the following linked list look like when each node is shifted 44328974278344432897427834 to the left.

34\rightarrow17\rightarrow17\rightarrow74\rightarrow83\rightarrow59\rightarrow39

×

Problem Loading...

Note Loading...

Set Loading...