Ask a Question

sanchayita

Open doubly linked lists Data type declarations record DoublyLinkedNode { prev // A reference to the previous node next // A reference to the next node data // Data or a reference to data } record DoublyLinkedList { DoublyLinkedNode firstNode // points to first node of list DoublyLinkedNode lastNode // points to last node of list } Traversing the list Forwards node := list.firstNode while node ≠ null node := node.next Backwards node := list.lastNode while node ≠ null node := node.prev Inserting a node function insertAfter(List list, Node node, Node newNode) newNode.prev := node newNode.next := node.next if node.next == null list.lastNode := newNode else node.next.prev := newNode node.next := newNode function insertBefore(List list, Node node, Node newNode) newNode.prev := node.prev newNode.next := node if node.prev == null list.firstNode := newNode else node.prev.next := newNode node.prev := newNode function insertBeginning(List list, Node newNode) if list.firstNode == null list.firstNode := newNode list.lastNode := newNode newNode.prev := null newNode.next := null else insertBefore(list, list.firstNode, newNode) function insertEnd(List list, Node newNode) if list.lastNode == null insertBeginning(list, newNode) else insertAfter(list, list.lastNode, newNode) Removing a node function remove(List list, Node node) if node.prev == null list.firstNode := node.next else node.prev.next := node.next if node.next == null list.lastNode := node.prev else node.next.prev := node.prev destroy node