What is best way of doubly linked list implement for java with features of insertation, deletation and replace ?
Add a comment
|
6 Answers
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.
Comments
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.
5 Comments
Reese Moore
This does absolutely nothing however by way of learning how a linked list works or is implemented.
aioobe
That's true. But that's not how I interpreted the question.
Reese Moore
He asked about implementing it, therefore one would assume that he doesn't just want to inherit another implementation.
brain
I think if mTuran wanted to learn about implementing a linked list he could google it a bit.
aioobe
@Reese, I provided him with a way of implementing it. At the same time I implicitly said that it sounds like
java.util.LinkedList is actually what he wants.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.
Comments
java.util.LinkedList<E> is already doubly linked, you can check out/modify the source if it does not match your needs.
Comments
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.
Comments
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();
}
}
