So here is another implementation of another linked list, Doubly-Linked List.

For a doubly-linked list, each node is divided into

 three parts: the left pointer field, the data field, and t

he right pointer field.

The left pointer field is used to contain the 

address of the preceding node in the list or what is known as the Predecessor

Unlike the sing

ly-linked list counterpart, the doubly-linked list can traverse backwards since there is a pointer to poin

t at the previous node.

The algorithms:

-       Inserting a Node into a Doubly-Linked List

o    General procedure

1.     Create a new node for the element

2.     Set the data field of the new node to the value to be inse

rted.

3.     Determine the position of the node in the list based on its valu

e

4.     Insert the node

-       Inserting a node into the Head of the List

o    The algorithm

1.     Set the left pointer field of the new node to null

2.     Set the right pointer field of the new node to the address contained in the head.

3.     Set the left pointer filed of the current head node in the list to the address of the new node.

-       Insert a Node at the End of a List

o    The algorithm:

1.     Set the right pointer field  of the new node to null

2.     Set the left pointer field of the new node to tail

3.     Set the right pointer field of the current tail node in the list to the address of the new node.

4.     Set the variable tail to the address of the new node.

-       Inserting a node within the list

o    The algorithm:

1.     Determine the position of the node in the list

2.     Set the left pointer field of the new node to the address of the current node.

3.     Set the right pointer field of the new node to the address of the current.next node.

4.     Set the right pointer field of the current node to the address of the new node

5.     Set the left pointer field of the current.next node to the address of the new node.

-       Deleting a node from a doubly-linked list

o    General procedure

1.     Locate the node

2.     Delete the node

3.     Release the node form memory

-       Deleting the node at the Head of the list

o    The Algorithm

1.     Set the variable head to the address of the second node in the list.

2.     Set the left pointer field of the new head node to null

-       Deleting the node from within the list

o    The Algorithm

1.     Set the right pointer field of current.previous node to the address of the current.next node

Set the left pointer field of the current.next node to the address of the current.previous node

The code and the output:

Click here to download the code.

For this implementation of a linked list in Java, I created my own class for a node called SLNode since a different node is needed for a singly and a doubly.

Here is the SLNode class:

class SLNode

{

public Object data;

public SLNode next;

public SLNode(Object d)

{

data=d;

next=null;

}

}

The next code is the class for the singly linked list called the SLinkedList

The attributes:

SLNode head;

SLNode tail;

We only need two attribute since a singlylinked list only has a head and a tail

The constructor:

public SLinkedList()

{

head=null;

tail=null;

}

It all attributes are set to null since from the beggining, the list is empty.

3 methods for adding data. Why 3? It is because there are three situations to take note when adding data within a singly linked list namely: when adding at the beginning, at the middle (1<1

public void addFirst(SLNode newNode) //add at the beginning

{

newNode.next=head;

head=newNode;

}

public void addLast(SLNode newNode) //add at the end of the list

{

tail.next=newNode;

tail=newNode;

}

public void add(SLNode newNode, int pos) //add at a specified position

{

SLNode current = head;

SLNode previous = head;

int ctr=0;

if(head!=null && tail!=null) //if list is not empty

{

while(current != null)

{

ctr++;

if(ctr == pos)

{

if(ctr==1)

addFirst(newNode);

else

{

newNode.next=current;

previous.next=newNode;

}

return;

}

previous = current;

current = current.next;

}

}

else //if list is empty

{

System.out.println("The list is empty. The node was added as the first and the last node.");

addFirst(newNode);

tail=head;

return;

}

addLast(newNode);

if(pos > ctr+1)

System.out.println("The desired position is still unavailable."

+ "\nThe node was inserted at position " + ctr

+ " which is considered as the last position.");

}

When deleting an item within the list, you only need to consider 2 things: if deleting the beginning of deleting the end. In this implementation, I incoporate the two situations into one function. But the 2 situations are still noted. Also, in the codes presented, two functions are presented, first if deleting based on the object you want to delete and the other is based on the what node you want to delete (eg. Node #2 or the 2nd Node)

public SLNode delete(Object data) //delete based on the item you want to delete

{

SLNode current=head;

SLNode previous=head;

int ctr=0;

while(current!=null)

{

ctr++;

if(current.data==data)

{

if(ctr==1)

head=head.next;

else if(ctr==length())

{

previous.next=null;

tail=previous;

}

else

previous.next=current.next;

return current;

}

previous=current;

current=current.next;

}

return null;

}

public SLNode delete(int i) //delete based on what node you want to delete starting at 1

{

SLNode current=head;

SLNode previous=head;

int ctr=0;

while(current!=null)

{

ctr++;

if(ctr==i)

{

if(ctr==1)

head=head.next;

else if(ctr==length())

{

previous.next=null;

tail=previous;

}

else

previous.next=current.next;

return current;

}

previous=current;

current=current.next;

}

return null;

}

The other methods are just accessory for extra functions for the SLinkedList class

public boolean search(Object node) //search a data based on a given key

{ //if found return true, else false

SLNode current=head;

while(current!=null)

if(current==node)

return true;

return false;

}

public SLNode getAt(int i) //this is similary to peek 

//returning a value at a given Node number

{

SLNode current=head;

int ctr=0;

while(current!=null)

{ 

ctr++;

if(ctr==i)

return current;

current=current.next;

}

return null;

}

public int length() //returns the current length/size of the list

{

int ctr=0;

SLNode current=head;

while(current!=null)

{

ctr++;

current=current.next;

}

return ctr;

}

Here are some codes on the implementation of the Singly-Linked List

public static void main(String args[])  

{  

SLinkedList list=new SLinkedList();  

list.add(new SLNode((Object)"Abcd"),2);  

list.add(new SLNode((Object)"CDeFG"),2);  

list.add(new SLNode("HigjDH"),2);

System.out.println("\nThe list size is now " + list.length());

displayList(list); System.out.println(list.delete(2));

displayList(list);

}

public static void displayNode(SLNode node) // to display the data of a single node

{

System.out.print(node.data);

}

public static void displayList(SLinkedList list) // to display the an entire list

{

SLNode current=list.head;

int ctr=0;

while(current!=null)

{

ctr++;

System.out.print("Node " + ctr + " ");

displayNode(current);

System.out.println();

current = current.next;

}

}