如何在Java中实现循环链表？
How to implements circular linked list in Java?
我有一个项目需要在不使用 API 的情况下实施循环比对列表。我完成了大部分代码，但由于某些原因我无法获得我正在寻找的输出。我恳请任何可以帮助我解决问题的人。一个具体问题是我无法将指针从我在 find 方法中找到的键开始迭代。例如如果数组元素为 10、9、8、5、6。如果我将 8 作为参数传递给 find 方法，如果找到它，它应该显示为 8、5、6、10、9 等。否则保持元素不变。
下面是我准备好的代码，请查看它下面的输出，我想这会帮助您弄清楚我在寻找什么。密切关注我的插入、查找、步骤方法。提前谢谢你！`
//LinkFirstLast Classs
class LinkFirstLast {
public long theData;
public LinkFirstLast next;
public LinkFirstLast last;
public LinkFirstLast previous;
public LinkFirstLast() {
}
public LinkFirstLast(int data) {
theData =data;
}
public void displayLink(){
System.out.print(theData+ " ");
}
}
// Circular linklist class//////////////////
class CircList {
private LinkFirstLast first, last;
int nItems;
//Constructor
public CircList(){
last = null;
}
//Creates a node and inserts new data
public void insert(int data) {
LinkFirstLast newLink = new LinkFirstLast(data);
if(isEmpty()){
last = newLink;
// first = newLink;
}
else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
//last.next = first;
// first.previous = last;
nItems++;
}
public void displayList() {
LinkFirstLast current = first;
while(current != null){
current.displayLink();
current =current.next;
}
System.out.println("");
}
public LinkFirstLast find(int key) {
LinkFirstLast current = first;
while(current != null && current.theData != key){
if(current.theData == key){
first = current;
first = current.next;
last.next = first;
}
else{
current = current.next;
}
}
/*
first.previous = newLink;
newLink.next = first;
first = newLink;
LinkFirstLast current = first;
while(current != null && current.theData != key )
{
current = current.next;
}
*/
return current;
}
public LinkFirstLast delete() {
LinkFirstLast current;
current = first;
while(first.next == null){
last = null;
}
first = first.next;
return current;
}
public int getSize() {
return nItems;
}
public void step() {
System.out.print("List: ");
if(first != null && first.next !=null){
first.next= first.next;
}
}
//Checks if linkedlist has no item
public boolean isEmpty() {
return (nItems==0);
}
public LinkFirstLast delete(int key) {
LinkFirstLast current = first;
LinkFirstLast previous = first;
while(current.theData != key)
{
if(current.next == null)
return null;
else
{
previous = current;
current = current.next;
}
}
if(current == first)
first = first.next;
else
previous.next = current.next;
nItems--;
return current;
}
// -------------------------------------------------------------
}
// main
class Pro {
public static void main(String[] args)
{
LinkFirstLast f, d;
CircList theList = new CircList(); // make list
theList.insert(10); // insert items
theList.insert(20);
theList.insert(30);
theList.insert(40);
theList.insert(50);
theList.insert(60);
theList.insert(70);
theList.displayList();
f = theList.find(30);
if( f != null){
System.out.println("Found link with key " + f.theData);
}
else{
System.out.println("Can't find link with key 30");
}
theList.displayList(); // display list
System.out.println("Inserting link with key 80");
theList.insert(80);
theList.displayList(); // display list
d = theList.delete(60); // delete item
if( d != null )
System.out.println("Deleted link with key " + d.theData);
else
System.out.println("Can't delete link with key 60");
theList.displayList(); // display list
f = theList.find(99); // find item
if( f != null){
System.out.println("Found link with key " + f.theData);}
else
System.out.println("Can't find link with key 99" );
theList.displayList(); // display list
d = theList.delete(13); // delete item
if( d != null )
System.out.println("Deleted link with key " + d.theData);
else
System.out.println("Can't delete link with key 13");
theList.displayList(); // display list
System.out.println("Stepping through list");
for(int j=0; j<theList.getSize(); j++)
{
theList.step();
theList.displayList();
}
System.out.println("Will delete and step one by one");
while(theList.isEmpty() == false)
{
theList.delete();
theList.step();
theList.displayList();
}
} // end main()
} // end class CircApp
输出为：
List: 70 60 50 40 30 20 10
Found link with key 30
List: 30 20 10 70 60 50 40
Inserting link with key 80
List: 80 30 20 10 70 60 50 40
Deleted link with key 60
List: 50 40 80 30 20 10 70
Can't find link with key 99
List: 50 40 80 30 20 10 70
Can't delete link with key 13
List: 50 40 80 30 20 10 70
Stepping through list
List: 40 80 30 20 10 70 50
List: 80 30 20 10 70 50 40
List: 30 20 10 70 50 40 80
List: 20 10 70 50 40 80 30
List: 10 70 50 40 80 30 20
List: 70 50 40 80 30 20 10
List: 50 40 80 30 20 10 70
Will delete and step one by one
List: 80 30 20 10 70 40
List: 20 10 70 40 30
List: 70 40 30 10
List: 30 10 40
List: 40 10
List: 10
List:
您的代码存在几个问题：
- classFirstLastLinkedList
的定义不好
- 这些方法没有做它们应该做的事情。
此外，没有任何地方表明列表到此结束。我已经在我的代码中做到了。
你的输出也不一致；我相信我的程序会更好地给你洞察力。我也添加了我的代码的输出。
我把代码留给你看。如果您在理解上有任何困难，请在下面发表评论：-
/**
*
* @author ssuman
*/
class FirstLastLinkedList{
protected long data;
protected FirstLastLinkedList next;
protected FirstLastLinkedList() {
}
}
class CircularLinkedList {
private FirstLastLinkedList head = null,temp = null, move = null, prev = null;
// `temp` is used to store the last node just before the `head` node;
protected void findInList(int userData){
if(head==null){
System.out.println("Can't find link with key "+ userData+"; List is empty!");
return;
}
move = head;
do{
if(move.data == userData){
System.out.println("Found link with key "+ userData);
return;
}
move = move.next;
}while(move != head);
System.out.println("Can't find link with key "+ userData);
}
protected void deleteFromList(int userData){
prev = move = head;
if(head==null){
System.out.println("Can't delete link with key "+ userData+"; List is empty!");
return;
}
do{
if(move.data == userData){
prev = getPreviousNodeInList(move);
head = move = move.next;
prev.next = move;
System.out.println("Deleted link with key "+ userData);
displayList();
return;
}
prev = move;
move = move.next;
}while(move != head);
System.out.println("Can't delete link with key "+ userData);
}
protected FirstLastLinkedList getPreviousNodeInList(FirstLastLinkedList current){
move = head;
if(current == null){
return null;
}
do{
if(head == current){
return temp;
}
if(move == current){
return prev;
}
prev = move;
move = move.next;
}while(move != head);
return null;
}
protected void insertInList(int userData){
if(head==null){
head = new FirstLastLinkedList();
System.out.println("Inserting Link with key "+userData);
head.data = userData;
head.next = null;
move = head;
}
else{
temp = new FirstLastLinkedList();
System.out.println("Inserting Link with key "+userData);
temp.data = userData;
move.next = temp;
move = temp;
}
}
protected void endList(){
temp.next = head;
}
protected void stepThroughList(){
if(head == null){
System.out.println("List is empty...");
return;
}
FirstLastLinkedList temporary;
System.out.println("Stepping through List :- ");
temporary = head;
do{
move = temporary;
do{
System.out.print(move.next.data+" ");
move = move.next;
}while(move != temporary);
temporary = temporary.next;
System.out.println("");
}while(temporary != head);
}
protected void deleteInStepsFromList(){
System.out.println("Will delete and step one by one :- ");
prev = move = head;
if(head==null){
System.out.println("Can't delete links ; List is empty!");
return;
}
do{
prev = getPreviousNodeInList(move);
head = move = move.next;
prev.next = move;
displayList();
}while(move != prev);
}
protected void displayList(){
move = head;
System.out.print("List : ");
do{
System.out.print(move.data+" ");
move = move.next;
}while(move != head);
System.out.println();
}
}
public class TestCircularLinkedList{
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.insertInList(10);
cll.insertInList(20);
cll.insertInList(30);
cll.insertInList(40);
cll.insertInList(50);
cll.insertInList(60);
cll.insertInList(70);
System.out.println("The List ended here...");
cll.endList();
cll.stepThroughList();
cll.findInList(10);
cll.findInList(33);
cll.displayList();
cll.deleteFromList(100);
cll.deleteInStepsFromList();
}
}
输出：-
Inserting Link with key 10
Inserting Link with key 20
Inserting Link with key 30
Inserting Link with key 40
Inserting Link with key 50
Inserting Link with key 60
Inserting Link with key 70
The List ended here...
Stepping through List :-
20 30 40 50 60 70 10
30 40 50 60 70 10 20
40 50 60 70 10 20 30
50 60 70 10 20 30 40
60 70 10 20 30 40 50
70 10 20 30 40 50 60
10 20 30 40 50 60 70
Found link with key 10
Can't find link with key 33
List : 10 20 30 40 50 60 70
Can't delete link with key 100
Will delete and step one by one :-
List : 20 30 40 50 60 70
List : 30 40 50 60 70
List : 40 50 60 70
List : 50 60 70
List : 60 70
List : 70
我有一个项目需要在不使用 API 的情况下实施循环比对列表。我完成了大部分代码，但由于某些原因我无法获得我正在寻找的输出。我恳请任何可以帮助我解决问题的人。一个具体问题是我无法将指针从我在 find 方法中找到的键开始迭代。例如如果数组元素为 10、9、8、5、6。如果我将 8 作为参数传递给 find 方法，如果找到它，它应该显示为 8、5、6、10、9 等。否则保持元素不变。
下面是我准备好的代码，请查看它下面的输出，我想这会帮助您弄清楚我在寻找什么。密切关注我的插入、查找、步骤方法。提前谢谢你！`
//LinkFirstLast Classs
class LinkFirstLast {
public long theData;
public LinkFirstLast next;
public LinkFirstLast last;
public LinkFirstLast previous;
public LinkFirstLast() {
}
public LinkFirstLast(int data) {
theData =data;
}
public void displayLink(){
System.out.print(theData+ " ");
}
}
// Circular linklist class//////////////////
class CircList {
private LinkFirstLast first, last;
int nItems;
//Constructor
public CircList(){
last = null;
}
//Creates a node and inserts new data
public void insert(int data) {
LinkFirstLast newLink = new LinkFirstLast(data);
if(isEmpty()){
last = newLink;
// first = newLink;
}
else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
//last.next = first;
// first.previous = last;
nItems++;
}
public void displayList() {
LinkFirstLast current = first;
while(current != null){
current.displayLink();
current =current.next;
}
System.out.println("");
}
public LinkFirstLast find(int key) {
LinkFirstLast current = first;
while(current != null && current.theData != key){
if(current.theData == key){
first = current;
first = current.next;
last.next = first;
}
else{
current = current.next;
}
}
/*
first.previous = newLink;
newLink.next = first;
first = newLink;
LinkFirstLast current = first;
while(current != null && current.theData != key )
{
current = current.next;
}
*/
return current;
}
public LinkFirstLast delete() {
LinkFirstLast current;
current = first;
while(first.next == null){
last = null;
}
first = first.next;
return current;
}
public int getSize() {
return nItems;
}
public void step() {
System.out.print("List: ");
if(first != null && first.next !=null){
first.next= first.next;
}
}
//Checks if linkedlist has no item
public boolean isEmpty() {
return (nItems==0);
}
public LinkFirstLast delete(int key) {
LinkFirstLast current = first;
LinkFirstLast previous = first;
while(current.theData != key)
{
if(current.next == null)
return null;
else
{
previous = current;
current = current.next;
}
}
if(current == first)
first = first.next;
else
previous.next = current.next;
nItems--;
return current;
}
// -------------------------------------------------------------
}
// main
class Pro {
public static void main(String[] args)
{
LinkFirstLast f, d;
CircList theList = new CircList(); // make list
theList.insert(10); // insert items
theList.insert(20);
theList.insert(30);
theList.insert(40);
theList.insert(50);
theList.insert(60);
theList.insert(70);
theList.displayList();
f = theList.find(30);
if( f != null){
System.out.println("Found link with key " + f.theData);
}
else{
System.out.println("Can't find link with key 30");
}
theList.displayList(); // display list
System.out.println("Inserting link with key 80");
theList.insert(80);
theList.displayList(); // display list
d = theList.delete(60); // delete item
if( d != null )
System.out.println("Deleted link with key " + d.theData);
else
System.out.println("Can't delete link with key 60");
theList.displayList(); // display list
f = theList.find(99); // find item
if( f != null){
System.out.println("Found link with key " + f.theData);}
else
System.out.println("Can't find link with key 99" );
theList.displayList(); // display list
d = theList.delete(13); // delete item
if( d != null )
System.out.println("Deleted link with key " + d.theData);
else
System.out.println("Can't delete link with key 13");
theList.displayList(); // display list
System.out.println("Stepping through list");
for(int j=0; j<theList.getSize(); j++)
{
theList.step();
theList.displayList();
}
System.out.println("Will delete and step one by one");
while(theList.isEmpty() == false)
{
theList.delete();
theList.step();
theList.displayList();
}
} // end main()
} // end class CircApp
输出为：
List: 70 60 50 40 30 20 10
Found link with key 30
List: 30 20 10 70 60 50 40
Inserting link with key 80
List: 80 30 20 10 70 60 50 40
Deleted link with key 60
List: 50 40 80 30 20 10 70
Can't find link with key 99
List: 50 40 80 30 20 10 70
Can't delete link with key 13
List: 50 40 80 30 20 10 70
Stepping through list
List: 40 80 30 20 10 70 50
List: 80 30 20 10 70 50 40
List: 30 20 10 70 50 40 80
List: 20 10 70 50 40 80 30
List: 10 70 50 40 80 30 20
List: 70 50 40 80 30 20 10
List: 50 40 80 30 20 10 70
Will delete and step one by one
List: 80 30 20 10 70 40
List: 20 10 70 40 30
List: 70 40 30 10
List: 30 10 40
List: 40 10
List: 10
List:
您的代码存在几个问题：
- classFirstLastLinkedList 的定义不好
- 这些方法没有做它们应该做的事情。
此外，没有任何地方表明列表到此结束。我已经在我的代码中做到了。
你的输出也不一致；我相信我的程序会更好地给你洞察力。我也添加了我的代码的输出。
我把代码留给你看。如果您在理解上有任何困难，请在下面发表评论：-
/**
*
* @author ssuman
*/
class FirstLastLinkedList{
protected long data;
protected FirstLastLinkedList next;
protected FirstLastLinkedList() {
}
}
class CircularLinkedList {
private FirstLastLinkedList head = null,temp = null, move = null, prev = null;
// `temp` is used to store the last node just before the `head` node;
protected void findInList(int userData){
if(head==null){
System.out.println("Can't find link with key "+ userData+"; List is empty!");
return;
}
move = head;
do{
if(move.data == userData){
System.out.println("Found link with key "+ userData);
return;
}
move = move.next;
}while(move != head);
System.out.println("Can't find link with key "+ userData);
}
protected void deleteFromList(int userData){
prev = move = head;
if(head==null){
System.out.println("Can't delete link with key "+ userData+"; List is empty!");
return;
}
do{
if(move.data == userData){
prev = getPreviousNodeInList(move);
head = move = move.next;
prev.next = move;
System.out.println("Deleted link with key "+ userData);
displayList();
return;
}
prev = move;
move = move.next;
}while(move != head);
System.out.println("Can't delete link with key "+ userData);
}
protected FirstLastLinkedList getPreviousNodeInList(FirstLastLinkedList current){
move = head;
if(current == null){
return null;
}
do{
if(head == current){
return temp;
}
if(move == current){
return prev;
}
prev = move;
move = move.next;
}while(move != head);
return null;
}
protected void insertInList(int userData){
if(head==null){
head = new FirstLastLinkedList();
System.out.println("Inserting Link with key "+userData);
head.data = userData;
head.next = null;
move = head;
}
else{
temp = new FirstLastLinkedList();
System.out.println("Inserting Link with key "+userData);
temp.data = userData;
move.next = temp;
move = temp;
}
}
protected void endList(){
temp.next = head;
}
protected void stepThroughList(){
if(head == null){
System.out.println("List is empty...");
return;
}
FirstLastLinkedList temporary;
System.out.println("Stepping through List :- ");
temporary = head;
do{
move = temporary;
do{
System.out.print(move.next.data+" ");
move = move.next;
}while(move != temporary);
temporary = temporary.next;
System.out.println("");
}while(temporary != head);
}
protected void deleteInStepsFromList(){
System.out.println("Will delete and step one by one :- ");
prev = move = head;
if(head==null){
System.out.println("Can't delete links ; List is empty!");
return;
}
do{
prev = getPreviousNodeInList(move);
head = move = move.next;
prev.next = move;
displayList();
}while(move != prev);
}
protected void displayList(){
move = head;
System.out.print("List : ");
do{
System.out.print(move.data+" ");
move = move.next;
}while(move != head);
System.out.println();
}
}
public class TestCircularLinkedList{
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.insertInList(10);
cll.insertInList(20);
cll.insertInList(30);
cll.insertInList(40);
cll.insertInList(50);
cll.insertInList(60);
cll.insertInList(70);
System.out.println("The List ended here...");
cll.endList();
cll.stepThroughList();
cll.findInList(10);
cll.findInList(33);
cll.displayList();
cll.deleteFromList(100);
cll.deleteInStepsFromList();
}
}
输出：-
Inserting Link with key 10
Inserting Link with key 20
Inserting Link with key 30
Inserting Link with key 40
Inserting Link with key 50
Inserting Link with key 60
Inserting Link with key 70
The List ended here...
Stepping through List :-
20 30 40 50 60 70 10
30 40 50 60 70 10 20
40 50 60 70 10 20 30
50 60 70 10 20 30 40
60 70 10 20 30 40 50
70 10 20 30 40 50 60
10 20 30 40 50 60 70
Found link with key 10
Can't find link with key 33
List : 10 20 30 40 50 60 70
Can't delete link with key 100
Will delete and step one by one :-
List : 20 30 40 50 60 70
List : 30 40 50 60 70
List : 40 50 60 70
List : 50 60 70
List : 60 70
List : 70