Last active
October 23, 2024 15:03
-
-
Save sedj601/93bc06e03be4ea5771247be5d8ccff96 to your computer and use it in GitHub Desktop.
Doubly LinkedList Alpha Ordered
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class DoublyLinkedList { | |
//A node class for doubly linked list | |
class Node{ | |
String name; | |
Node previous; | |
Node next; | |
public Node(String name) { | |
this.name = name; | |
} | |
} | |
//Initially, heade and tail is set to null | |
Node head, tail = null; | |
//add a node to the list | |
public void addNode(String item) { | |
//Create a new node | |
Node newNode = new Node(item); | |
//if list is empty, head and tail points to newNode | |
if(head == null) { | |
head = tail = newNode; | |
//head's previous will be null | |
head.previous = null; | |
//tail's next will be null | |
tail.next = null; | |
} | |
else { | |
//add newNode to the end of list. tail->next set to newNode | |
tail.next = newNode; | |
//newNode->previous set to tail | |
newNode.previous = tail; | |
//newNode becomes new tail | |
tail = newNode; | |
//tail's next point to null | |
tail.next = null; | |
} | |
} | |
public void addOrderedNode(String item) { | |
//Create a new node | |
Node newNode = new Node(item); | |
//if list is empty, head and tail points to newNode | |
if(head == null) { | |
head = tail = newNode; | |
//head's previous will be null | |
head.previous = null; | |
//tail's next will be null | |
tail.next = null; | |
} | |
else { | |
//add newNode to the end of list. tail->next set to newNode | |
if(newNode.name.compareTo(head.name) < 0) | |
{ | |
Node tempNode = head; | |
head = newNode; | |
head.next = tempNode; | |
tail = tempNode; | |
} | |
else | |
{ | |
Node frontNode = findInsertAfterNode(newNode, head); | |
if(frontNode != null) | |
{ | |
Node backNode = frontNode.next; | |
frontNode.next = newNode; | |
backNode.previous = newNode; | |
} | |
else | |
{ | |
Node tempNode = tail; | |
tempNode.next = newNode; | |
tail = newNode; | |
} | |
} | |
} | |
} | |
public void print() | |
{ | |
printNode(head); | |
} | |
private Node findInsertAfterNode(Node nodeToBeInserted, Node currentCheck) | |
{ | |
if(nodeToBeInserted == null || currentCheck == null) | |
{ | |
return null; | |
} | |
else if(nodeToBeInserted.name.compareTo(currentCheck.name) < 0) | |
{ | |
return currentCheck; | |
} | |
else | |
{ | |
return findInsertAfterNode(nodeToBeInserted, currentCheck.next); | |
} | |
} | |
private void printNode(Node node) | |
{ | |
if(node == null) | |
{ | |
System.out.println(""); | |
} | |
else | |
{ | |
System.out.print(node.name + "\t"); | |
printNode(node.next); | |
} | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* | |
* @author blj0011 | |
*/ | |
public class JavaTestArea { | |
public static void main(String[] args) { | |
DoublyLinkedList doublyLinkedList = new DoublyLinkedList(); | |
doublyLinkedList.print(); | |
doublyLinkedList.addOrderedNode("Cherry"); | |
doublyLinkedList.print(); | |
doublyLinkedList.addOrderedNode("Banana"); | |
doublyLinkedList.print(); | |
doublyLinkedList.addOrderedNode("Apple"); | |
doublyLinkedList.print(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Edited code from: https://www.softwaretestinghelp.com/doubly-linked-list-in-java/
I didn't do any test outside of the test in JavaTestArea. There may be issues with this code!
Ignore the comments in this code. I did not update the comments! I altered the code!