6: double linked list (creat, insert)

Double Linked List
Every node stores a reference to its previous node as well as its next. This is good if you need to move back by a few nodes and don t want to run from the beginning of the list.
Double Linked lists Declaration
Here’s part of the definition of Link. It contains data and two pointers to the
Before and after link:
public class DBLL
{
int data; // value of element
DBLL before; // reference to previous node
DBLL after; // reference to next node
public DBLL (int d) // constructor
{
data = d ;
}
}
Here’s part of the creation of double liked list.
Where head and tail are static DBLL.
Public create()
{ DBLL head, tail;
Input value of data d
Head = new DBLL (d) ; // create the first node
College of Information Technology / Software Department
………………………………………………………..
Data Structures / Second Class / 2017-2018
LEC. 5
28
DBLL p = head;
For (int i=1 ; i<=n-1 ; i++) // n is the number of nodes
Input value of data d
tail = new DBLL (d) ;
tail . before = p ;
p . after = tail ;
p = tail;
} // create
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Double-Linked List, Insertion Operation.
The insertfirst() method
The insertfirst() method of linklist inserts a new link at the beginning of the list. The insertion it can be done in two steps:
1. Update the after link of a new node, to point to the current head node.
2. Update the before link of a current head node, to point to a new node.
3. Update head link to point to the new node.
Input value of data d
n ++ ;
If (head = = null) // There is no linked list
head = new DBLL (d) ;
tail = head ;
else
DBLL p = new DBLL (d) ;
p . after = head ;
head . before = p ;
head = p ;