Circular Linked List - Links as Sub Class¶
Key Ideas¶
- The doubly linked list allows the list to be traversed in both directions; forwards and backwards
- In a circular doubly-linked list the last node (next) points to the first. The first node (previous) points to the last node.
- The doubly linked list allows the list to be traversed in both directions; forwards and backwards
Note
Not all languages support subclasses.
Lecture Code¶
package com.mycompany.linkedlistcircular;
/*
* Programmer: James Goudy
* Project Circular LinkedList
*
* NOTE: last link is referenced as first.prev
*/
class CircularLinkedList {
Link first = new Link("");
// ---------------------------------
// sub class - Link / Nodes
// NOTE: this can be a separate class as well
class Link {
Link first = null;
// data
String city = null;
// link navigation
Link next = null;
Link prev = null;
// constructor
Link(String city) {
this.city = city;
this.next = null;
this.prev = null;
}
public void displayNode() {
System.out.print(city + " ");
}
} // end of link
// ---------------------------------
// constructor
public CircularLinkedList() {
first = null;
}
// add link at the beginning of the list
public boolean addFirst(String city) {
Link newLink = new Link(city);
if (first == null) {
// empty list
newLink.next = newLink;
newLink.prev = newLink;
first = newLink;
} else {
// connect the newLink references
newLink.next = first;
newLink.prev = first.prev;
first.prev = newLink;
// move first to the new link
first = newLink;
// point the last link to the new first
first.prev.next = first;
}
return true;
}
// add link to the end of the list
public boolean addLast(String city) {
Link newLink = new Link(city);
if (first == null) {
//list is empty
first = newLink;
} else {
// set new link references
newLink.next = first;
newLink.prev = first.prev;
// last link is (first.prev)
first.prev.next = newLink;
first.prev = newLink;
}
return true;
}
public boolean findCity(String citySearch) {
if (first == null) {
// if list is empty
return false;
} else {
Link current = first;
do {
if (current.city.equals(citySearch)) {
return true;
}
current = current.next;
} while (current != first);
return false;
}
}
public boolean insertAfter(String citySearch, String insertCity) {
Link newLink = new Link(insertCity);
if (first == null) {
// list is empty - add the link
first = newLink;
// NOTE: there is an option not to insert
// a link then the code above would be replaced
// with return false
} else {
Link current = first;
while (current != null) {
if (current.city.equals(citySearch)) {
// check if last link
if (current.next == first.prev) {
// check if last link
current.next = newLink;
newLink.prev = current;
first.prev = newLink;
} else {
newLink.next = current.next;
newLink.prev = current;
current.next.prev = newLink;
current.next = newLink;
}
return true;
}
current = current.next;
}
}
return false;
}
public boolean insertBefore(String citySearch, String insertCity) {
Link newLink = new Link(insertCity);
if (first == null) {
// list is empty - add the link
first = newLink;
// NOTE: there is an option not to insert
// a link then the code above would be replaced
// with return false
} else {
Link current = first;
while (current != null) {
if (current.city.equals(citySearch)) {
// check for first link
if (current.prev == null) {
// check if last link
current.prev = newLink;
newLink.next = current;
first = newLink;
} else {
newLink.next = current;
newLink.prev = current.prev;
current.prev.next = newLink;
current.prev = newLink;
}
return true;
}
current = current.next;
}
}
return false;
}
public boolean deleteCity(String citySearch) {
if (first == null) {
return false;
} else {
Link current = first;
do {
if (current.city.equals(citySearch)) {
if (current.prev == null) {
// first node
current.next.prev = null;
first = current.next;
current = null;
return true;
} else if (current.next == null) {
// last node
current.prev.next = null;
first.prev = current;
current = null;
return true;
} else {
// a center node
current.prev.next = current.next;
current.next.prev = current.prev;
current = null;
return true;
}
}
current = current.next;
} while (current != first);
return false;
}
} //end of function
public void displayList() {
Link current = first;
System.out.println("\n** Display List Forward To Back **");
do {
current.displayNode();
current = current.next;
if (current == first) {
System.out.println("\n-----------\n");
return;
}
} while (current.next != null);
} // end of method
public void displayList(String startCity) {
Link current = first;
Link start = null;
System.out.println("\n ** Display List Forward To Back"
+ " starting at " + startCity + "**");
// find the city in the list
do {
if (current.city.equals(startCity)) {
break;
}
current = current.next;
if (current == first) {
System.out.println("City Not Found");
return;
}
} while (current.next != null);
System.out.println("");
start = current;
do {
current.displayNode();
current = current.next;
if (current == start) {
System.out.println("\n-----------\n");
return;
}
} while (current.next != null);
} // end of method
public void displayListReverse() {
Link current = first.prev;
System.out.println("\n** Display List in Reverse **\n");
do {
current.displayNode();
current = current.prev;
if (current == first.prev) {
System.out.println("\n-----------\n");
return;
}
} while (current.prev != null);
} // end of method
public void displayListReverse(String startCity) {
Link current = first;
Link start = null;
System.out.println("\n ** Display list in reverse"
+ " starting at " + startCity + "**");
// find the city in the list
do {
if (current.city.equals(startCity)) {
break;
}
current = current.next;
if (current == first) {
System.out.println("City Not Found");
return;
}
} while (current.next != null);
System.out.println("");
start = current;
do {
current.displayNode();
current = current.prev;
if (current == start) {
System.out.println("\n-----------\n");
return;
}
} while (current.prev != null);
} // end of method
} // end of class
public class DS_LinkedListCircular {
static CircularLinkedList dl = new CircularLinkedList();
public static void citySearch(String searchCity) {
// note that findCity returns a boolean
// so it can be used in an "if" statement
if (dl.findCity(searchCity)) {
System.out.println("\n" + searchCity + " is in list");
} else {
System.out.println("\n" + searchCity + " not found");
}
}
public static void deleteCity(String searchCity) {
// note that findCity returns a boolean
// so it can be used in an "if" statement
if (dl.deleteCity(searchCity)) {
System.out.println(searchCity + " was deleted");
} else {
System.out.println(searchCity + " was NOT deleted");
}
}
public static void main(String[] args) {
String searchCity = "";
String insertCity = "";
// insert data at front of list
dl.addFirst("Kali");
dl.addFirst("Polson");
dl.addFirst("Missoula");
dl.addFirst("Whitefish");
dl.addFirst("Plains");
// insert data at end of list
dl.addLast("Chicago");
dl.addLast("Denver");
dl.addLast("Sandiego");
dl.displayList();
dl.displayListReverse();
dl.displayList("Missoula");
dl.displayList("Wolfcreek");
dl.displayListReverse();
dl.displayListReverse("Missoula");
System.out.println("\n----- Find Examples------\n");
searchCity = "Missoula";
citySearch(searchCity);
searchCity = "Bozeman";
citySearch(searchCity);
System.out.println("\n----- Delete Examples------\n");
searchCity = "Polson";
deleteCity(searchCity);
searchCity = "Bozeman";
deleteCity(searchCity);
searchCity = "Sandiego";
deleteCity(searchCity);
searchCity = "Whitefish";
deleteCity(searchCity);
dl.displayList();
System.out.println("\n----- Insert After Examples------\n");
searchCity = "Missoula";
insertCity = "Dayton";
dl.insertAfter(searchCity, insertCity);
searchCity = "Denver";
insertCity = "Boulder";
dl.insertAfter(searchCity, insertCity);
dl.displayList();
System.out.println("\n----- Insert After Examples------\n");
searchCity = "Chicago";
insertCity = "Springfield";
dl.insertBefore(searchCity, insertCity);
searchCity = "Missoula";
insertCity = "Libby";
dl.insertBefore(searchCity, insertCity);
dl.displayList();
System.out.println("\nbye");
}
}
/*
* output
*
** Display List Forward To Back **
* Plains Whitefish Missoula Polson Kali Chicago Denver Sandiego
* -----------
*
*
** Display List in Reverse **
*
* Sandiego Denver Chicago Kali Polson Missoula Whitefish Plains
* -----------
*
*
** Display List Forward To Back starting at Missoula**
*
* Missoula Polson Kali Chicago Denver Sandiego Plains Whitefish
* -----------
*
*
** Display List Forward To Back starting at Wolfcreek**
* City Not Found
*
** Display List in Reverse **
*
* Sandiego Denver Chicago Kali Polson Missoula Whitefish Plains
* -----------
*
*
** Display list in reverse starting at Missoula**
*
* Missoula Whitefish Plains Sandiego Denver Chicago Kali Polson
* -----------
*
*
* ----- Find Examples------
*
*
* Missoula is in list
*
* Bozeman not found
*
* ----- Delete Examples------
*
* Polson was deleted
* Bozeman was NOT deleted
* Sandiego was deleted
* Whitefish was deleted
*
** Display List Forward To Back **
* Plains Missoula Kali Chicago Denver
* -----------
*
*
* ----- Insert After Examples------
*
*
** Display List Forward To Back **
* Plains Missoula Dayton Kali Chicago Denver Boulder
* -----------
*
*
* ----- Insert After Examples------
*
*
** Display List Forward To Back **
* Plains Libby Missoula Dayton Kali Springfield Chicago Denver Boulder
* -----------
*
*
* bye
*
*/
End Of Topic