LinkedNodeList

0

Data structure

LinkedNodeList is a circular linked list. The class described here is used in apache kahadb.  Each node in the list knows its next node, previous node and whether it is a tail node. The LinkedNode can be enhanced so that it is part of a list and is aware of the list that owns it.

LinkedNodeList

The LinkedNodeList has a link to the header node, it is easy to reach to the header from any node in the list. We don’t have to traverse through the list. It is also easy to add a node or a node list to either first or last of the list.

 

LinkedNodeList

Class Diagram

LinkedNodeList

Head Node: The node whose previous node is a tale node.
Previous Node: Null if the previous node is a tale node.
Next Node: Null if the current node is a tail node
Get Head Node:Returns current node if it is a head. Returns next node if the current node is tail else will traverse through the previous node link till it finds the head node.
Get Tail Node:Returns current node if it is a tail. Returns previous node if the current node is head else will traverse through the next node link till it finds the tail node.

New Node

LinkedNodeList

 

 

Link a new node to the above created node.

LinkedNodeList

public void testLinkedNode() {

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        assertTrue(n2.isHeadNode());
        assertTrue(n2.isTailNode());
        n1.linkAfter(n2);
        assertTrue(n1.isHeadNode());
        assertFalse(n1.isTailNode());
        assertFalse(n2.isHeadNode());
        assertTrue(n2.isTailNode());
        assertNull(n1.getPrevious());
        assertEquals(n1, n2.getPrevious());
        assertEquals(n2, n1.getNext());
        assertNull(n2.getNext());
        assertFalse(n2.isHeadNode());
        assertTrue(n2.isTailNode());
    }

Link node after the tail node

 

LinkedNodeList

Link node after the head node

 

LinkedNodeList

Link node which is a part of another circular linked list

 

 

 

LinkedNodeList

Unlink

 

LinkedNodeList

 

 

Share.

Leave A Reply