How do I implement a Doubly Linked List in Java?

What is best way of doubly linked list implement for java with feature开发者_开发百科s of insertation, deletation and replace ?

---

Have a private inner class called Node which represents the data in the list, which has a next node, a previous node, and a data value, and a way of getting and setting each.

---

Unless this is homework (in which case you should tag it as such), it would be hard to do any better than this:

class MyLinkedList<T> extends java.util.LinkedList<T> {
}

From the docs:

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

---

If you are interested in how doubly-linked lists and some other data structures are implemented, I would recommend looking over Duane Bailey's book on data structures. It's available as a free pdf at:

http://www.cs.williams.edu/~bailey/JavaStructures/Book.html

It's a fairly straight-forward book, and he shows how all the different data structures can be implemented - there's a section that thoroughly covers your question. I found it very helpful in my studies of data structures and how they work; I hope you find it helpful too.

---

java.util.LinkedList<E> is already doubly linked, you can check out/modify the source if it does not match your needs.

---

Don't implement it yourself, use LinkedList. However I assume this is some sort of homework problem so perhaps you could look at the source code to LinkedList.

---

public class DoublyLL {

class Node{
    int data;
    Node prev;
    Node next;

    Node(int d)
    {
        data=d;
    }
}
Node head;

public void fadd(int data)//Adding at first
{
    Node n=new Node(data);
    n.next=head;//Making the new node as head
    n.prev=null;//assignig new node's prev value as null so that it becomes new head
    if(head!=null)
    {
        head.prev=n;//changing prev of head node from null to new node
    }
    head=n;//head pointing toward new node
}

public void ladd(int data) //adding at last
{
    Node n=new Node(data);
    Node last=head;  //Make the node at last as head
    n.next=null;    //Point the new node next value as null so that it becomes new 
//tail
    if(head==null)  //if the LL is empty then make the new node as hhead
    {
        n.prev=null; 
        head=n;
        return;
    }
    while(last.next!=null)  //while last is pointing as null
    {
        last=last.next;     
    }
    last.next=n;    //next value of last is pointing as null to become new tail
    n.prev=last; //and prev value is pointing toward last Node
 }

  public void delete(Node n,Node d) //deletion of node at head
  {
    if(head==null || d==null) //when the node to be deleted is null
    {
        return;
    }
    if(head==d)     //if the node to be deleted iss head
    {
        head=d.next;    //point thhe head towards new head
    }
    if(d.next!=null)    //Change next only if node to be deleted is NOT the last node
    {
        d.next.prev=d.prev;
    }
    if(d.prev!=null)    // Change prev only if node to be deleted is NOT the firstnode
    {
        d.prev.next=d.next;
    }
    return;
  }

 public void disp() //traversing
    { 
        Node curr=head;
    Node last=null; 
    while (curr!=null)
        {
        System.out.print(curr.data + " "); 
        last=curr; 
        curr=curr.next; 
        }
    System.out.println(); 
    } 

public static void main(String[] args)
{
    DoublyLL dl=new DoublyLL();
    dl.fadd(1);
    dl.fadd(131);
    dl.fadd(21);
    dl.fadd(22);
    dl.disp();
    dl.ladd(12);
    dl.disp();
    dl.ladd(2);
    dl.delete(dl.head,dl.head);
    dl.disp();
    }
}