Doubly linked lists java

How do I implement a Doubly Linked List in Java?

What is best way of doubly linked list implement for java with features of insertation, deletation and replace ?

6 Answers 6

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 extends java.util.LinkedList

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.

He asked about implementing it, therefore one would assume that he doesn’t just want to inherit another implementation.

@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:

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 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(); >> 

Related

Hot Network Questions

Subscribe to RSS

To subscribe to this RSS feed, copy and paste this URL into your RSS reader.

Site design / logo © 2023 Stack Exchange Inc; user contributions licensed under CC BY-SA . rev 2023.7.21.43541

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.

Источник

Class LinkedList

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null ).

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.

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be «wrapped» using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new LinkedList(. ));

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

This class is a member of the Java Collections Framework.

Источник

Class LinkedList

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null ).

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.

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be «wrapped» using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new LinkedList(. ));

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

This class is a member of the Java Collections Framework.

Источник

Java Doubly Linked List

Java Doubly Linked List is a type of Linked List where each node apart from storing data has two links. The first link points to the previous node and the other link points to the next node of the list. Doubly Linked List, also abbreviated as DLL is much like a Single Linked List. Both Linked lists contain a pointer to the next node and a data field to represent the actual value to be stored in the node. The main difference is that DLL contains a pointer to the previous node in the list i.e. nodes in DLL are aware of both the previous and the next node. In this article, we will have a look at Doubly Linked List in Java, explore few examples, and get to know its Implementation.

Web development, programming languages, Software testing & others

Syntax

There is no particular syntax for the Doubly Linked list in Java, but we will see How to declare the Doubly Linked List in Java. Before looking into a declaration of Doubly Linked List, let us see the Concept behind the implementation of Doubly Linked List.

Node in Double Linked List:

Prev Node

Data

Next Node

Here Prev Node and Next Node are pointers to previous and next elements of node respectively. ‘Data’ is the actual element where data is stored.

Below are some of the important terms we need to understand,

• Prev: Each link of linked list has a link to the previous node called Prev.
• Next: Each link of linked list has a link to the next node called Next
• Link: Each link of linked list can store data, known as element.
• LinkedList: It contains the connection link to the first link and the last link.

Algorithm

• Define a Node class that represents a node in the linked list. It should have 3 properties i.e. previous node, data, and the next node
• Define another class to create a Doubly Linked List with two nodes i.e head and tail. Initially, these values will be null.
• Create a function for adding nodes in the linked list,
• It will first check whether the head is null and then insert the node as the head.
• Both head and tail will then point to the new node.
• If the tail is not null, the new node will be inserted at the list end in such a way that the pointer of the new node will point to the tail.
• Thus, the new node will become a new tail.

Declaration of Node for Doubly Linked List in Java:

As we can see there is an extra declaration or a reference(Node prev) in the case of Doubly Linked List.

Basic Operations of Doubly Linked List

Below are the basic operations available for Doubly Linked List,

• Insertion: Adding an element at the beginning of the linked list
• Deletion: Deleting an element at the beginning of the linked list
• Insert After: Adding an element after an item of linked list
• Insert Last: Adding an element to the end of the linked list
• Delete Last: Deleting an element at the end of linked list
• Delete: Deleting an element from the linked list using a key.
• Display forward: Displaying complete list in forward manner
• Display backward: Displaying complete list in backward manner

Examples of Java Doubly Linked List

Below are the different examples of Java Doubly Linked List:

Example #1: Declaration of Node and Adding nodes to Display

public class DLL < class Node< public int data; public Node prevNode; public Node nextNode; public Node(int data) < this.data = data; >> Node headNode, tailNode = null; public void addDLLNode(int data) < Node newDLLNode = new Node(data); if(headNode == null) < headNode = tailNode = newDLLNode; headNode.prevNode = null; tailNode.nextNode = null; >else < tailNode.nextNode = newDLLNode; newDLLNode.prevNode = tailNode; tailNode = newDLLNode; tailNode.nextNode = null; >> public void displayNode() < Node currentNode = headNode; if(headNode == null) < System.out.println("Doubly Linked List is empty"); return; >System.out.println("Nodes in Doubly Linked List: "); while(currentNode != null) < System.out.print(currentNode.data + " "); currentNode = currentNode.nextNode; >> public static void main(String[] args) < DLL dLinkedList = new DLL(); dLinkedList.addDLLNode(9); dLinkedList.addDLLNode(7); dLinkedList.addDLLNode(5); dLinkedList.addDLLNode(3); dLinkedList.addDLLNode(1); dLinkedList.addDLLNode(3); dLinkedList.addDLLNode(5); dLinkedList.addDLLNode(7); dLinkedList.displayNode(); >>

So here we are creating a Node class to declare a Doubly Linked list and displaying the values of DLL.

Example #2: Delete at beginning of the linked list and display

public class DLL < class Node< public int data; public Node prevNode; public Node nextNode; public Node(int data) < this.data = data; >> public void displayNode() < Node tempNode = headNode; while (tempNode != null) < System.out.print(tempNode.data + "–>"); tempNode = tempNode.nextNode; > System.out.println("END"); > Node headNode, tailNode = null; public void addNode(int data) < Node newNode = new Node(data); if(headNode == null) < headNode = tailNode = newNode; headNode.prevNode = null; tailNode.nextNode = null; >else < tailNode.nextNode = newNode; newNode.prevNode = tailNode; tailNode = newNode; tailNode.nextNode = null; >> public void deleteInitialNode() < if(headNode == null) < System.out.println("Doubly Linked List is empty"); return; >else < if(headNode != tailNode) < headNode = headNode.nextNode; >else < headNode = tailNode = null; >> > void printNode() < Node currNode = headNode; if(headNode == null) < System.out.println("Doubly Linked List is empty"); return; >while(currNode != null) < System.out.print(currNode.data + " "); currNode = currNode.nextNode; >System.out.println(); > public static void main(String[] args) < DLL doublyLL = new DLL(); doublyLL.addNode(3); doublyLL.addNode(5); doublyLL.addNode(7); doublyLL.addNode(9); doublyLL.addNode(11); System.out.println("Doubly linked list: "); doublyLL.printNode(); doublyLL.addNode(15); doublyLL.addNode(17); doublyLL.addNode(19); doublyLL.deleteInitialNode(); doublyLL.addNode(21); System.out.println("Doubly Linked List after deleting at the beginning: "); doublyLL.printNode(); >>

So here, the node is deleted at the beginning of the linked list i.e. Node 3 is deleted/ removed.

DLL can be traversed in forwarding and backward directions. Delete operation in DLL can be more efficient if the node pointer to be deleted is given. Every Node in DLL requires extra space for the previous pointer. All operations require an extra pointer to be maintained.

With this, we shall conclude our topic “Java Doubly Linked List”. We have seen What Java Doubly Linked List is and how is it implemented in Java programming with few examples. We have also seen Algorithm for Doubly Linked List and have listed out few operations applicable to DLL. We have implemented Insertion and delete at first operations, likewise, there are other operations also available which you can work on.

Recommended Articles

This is a guide to Java Doubly Linked List. Here we discuss the Introduction, syntax, and how is it implemented in Java programming with examples with code implementation. You may also have a look at the following articles to learn more –

89+ Hours of HD Videos
13 Courses
3 Mock Tests & Quizzes
Verifiable Certificate of Completion
Lifetime Access
4.5

97+ Hours of HD Videos
15 Courses
12 Mock Tests & Quizzes
Verifiable Certificate of Completion
Lifetime Access
4.5

JAVA Course Bundle — 78 Courses in 1 | 15 Mock Tests
416+ Hours of HD Videos
78 Courses
15 Mock Tests & Quizzes
Verifiable Certificate of Completion
Lifetime Access
4.8

Источник