Skip to content

Instantly share code, notes, and snippets.

@sedj601
Last active October 23, 2024 15:03
Show Gist options
  • Save sedj601/93bc06e03be4ea5771247be5d8ccff96 to your computer and use it in GitHub Desktop.
Save sedj601/93bc06e03be4ea5771247be5d8ccff96 to your computer and use it in GitHub Desktop.
Doubly LinkedList Alpha Ordered
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);
}
}
}
/**
*
* @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();
}
}
@sedj601
Copy link
Author

sedj601 commented Oct 8, 2024

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment