循环 linked 列表 link 从后到前，无前参考
Circular linked list link rear to front without front reference
I am trying to implement number 6 in this picture
我主要是想制作一个循环 linked 列表，方法是制作一个从后节点到前节点的 link。但是在这个例子中，他们说不要使用对第一个节点的前端引用，所以我不确定如何在没有前端引用的情况下访问前端节点。
在添加和删除方法中，我只需要放一行代码
rear.setLink(front); 但是，如果没有前面的参考，我不知道该怎么做。这是我的代码，大部分是我们使用的教科书的修改代码
/*
* modified code from the book
*
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.NoSuchElementException;
//import edu.colorado.nodes.Node;
public class CircularLinkedList<E> implements Cloneable {
// File: LinkedQueue.java from the package edu.colorado.collections
// Complete documentation is available from the LinkedQueue link in:
// http://www.cs.colorado.edu/~main/docs/
// Invariant of the LinkedQueue class:
// 1. The number of items in the queue is stored in the instance variable
// manyNodes.
// 2. The items in the queue are stored in a linked list, with the front
// of the queue stored at the head node, and the rear of the queue at
// the final node.
// 3. For a non-empty queue, the instance variable front is the head
// reference of the linked list of items and the instance variable rear
// is the tail reference of the linked list. For an empty queue, both
// front and rear are the null reference.
private int manyNodes=0; //numberOf Nodes in list initialized to 0
//private Node<E> front;
private Node<E> rear;
/**
* Initialize an empty queue.
* <b>Postcondition:</b>
* This queue is empty.
**/
public <Node>CircularLinkedList( )
{
//front = null;
rear = null;
}
/**
* Put a new a new item in this queue.
* @param item
* the item to be pushed onto this queue
* <b>Postcondition:</b>
* The item has been pushed onto this queue.
* @exception OutOfMemoryError
* Indicates insufficient memory for increasing the queue's capacity.
* <b>Note:</b>
* An attempt to increase the capacity beyond
* <CODE>Integer.MAX_VALUE</CODE> will cause the queue to fail with an
* arithmetic overflow.
**/
public void add(E item)
{
Node cursor;
if (isEmpty( ))
{ // Insert first item.
rear = new Node<E>(item, null);
//rear = front;
}
else
{ // Insert an item that is not the first.
rear.addNodeAfter(item);
rear = rear.getLink( );
//for(cursor =rear; curs
// rear.setLink(CircularLinkedList.listposition(0)); //make link to front creating a circular linked List
}
manyNodes++;
}
/**
* Generate a copy of this queue.
* @return
* The return value is a copy of this queue. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to an <CODE>LinkedQueue</CODE> before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
**/
@SuppressWarnings("unchecked")
public CircularLinkedList<E> clone( )
{ // Clone a LinkedQueue<E>.
CircularLinkedList<E> answer;
Object[ ] cloneInfo;
try
{
answer = (CircularLinkedList<E>) super.clone( );
}
catch (CloneNotSupportedException e)
{
// This exception should not occur. But if it does, it would probably indicate a
// programming error that made super.clone unavailable. The most comon error
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
cloneInfo = Node.listCopyWithTail(rear);
// answer.front = (Node<E>) cloneInfo[0];
answer.rear = (Node<E>) cloneInfo[1];
return answer;
}
/**
* Determine whether this queue is empty.
* @return
* <CODE>true</CODE> if this queue is empty;
* <CODE>false</CODE> otherwise.
**/
public boolean isEmpty( )
{
return (manyNodes == 0);
}
/**
* Get the front item, removing it from this queue.
* <b>Precondition:</b>
* This queue is not empty.
* @return
* The return value is the front item of this queue, and the item has
* been removed.
* @exception NoSuchElementException
* Indicates that this queue is empty.
**/
public E remove( )
{
E answer;
if (manyNodes == 0)
// NoSuchElementException is from java.util and its constructor has no argument.
throw new NoSuchElementException("Queue underflow");
answer = rear.getData( );
// front = front.getLink( );
manyNodes--;
if (manyNodes == 0)
rear = null;
return answer;
//rear.setLink(front);
}
/**
* Accessor method to determine the number of itaems in this queue.
* @return
* the number of items in this queue
**/
public int size( )
{
return manyNodes;
}
public static void main(String[] args)
{
CircularLinkedList c1 = new CircularLinkedList();
c1.add(1);
c1.add(2);
c1.add(3);
c1.remove();
System.out.println("the data in the rear is " + c1.rear.getData());
//System.out.println("the data in the front is " + c1.front.getData());
// System.out.println("the data in node after rear is " + c1.rear.getLink().getData());
//System.out.println("this is because the rear links to the front making the Linked List circular");
}
}
下面是节点Class代码（不需要编辑）
class Node<E>
{
// Invariant of the Node class:
// 1. Each node has one reference to an E Object, stored in the instance
// variable data.
// 2. For the final node of a list, the link part is null.
// Otherwise, the link part is a reference to the
// next node of the list.
private E data;
private Node<E> link;
/**
* Initialize a node with a specified initial data and link to the next
* node. Note that the initialLink may be the null reference,
* which indicates that the new node has nothing after it.
* @param initialData
* the initial data of this new node
* @param initialLink
* a reference to the node after this new node--this reference may be null
* to indicate that there is no node after this new node.
* @postcondition
* This node contains the specified data and link to the next node.
**/
public Node(E initialData, Node<E> initialLink)
{
data = initialData;
link = initialLink;
}
/**
* Modification method to add a new node after this node.
* @param element
* the data to place in the new node
* @postcondition
* A new node has been created and placed after this node.
* The data for the new node is element. Any other nodes
* that used to be after this node are now after the new node.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for a new
* Node.
**/
public void addNodeAfter(E element)
{
link = new Node<E>(element, link);
}
/**
* Accessor method to get the data from this node.
* @param - none
* @return
* the data from this node
**/
public E getData( )
{
return data;
}
/**
* Accessor method to get a reference to the next node after this node.
* @param - none
* @return
* a reference to the node after this node (or the null reference if there
* is nothing after this node)
**/
public Node<E> getLink( )
{
return link;
}
/**
* Copy a list.
* @param source
* the head of a linked list that will be copied (which may be
* an empty list in where source is null)
* @return
* The method has made a copy of the linked list starting at
* source. The return value is the head reference for the
* copy.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for the new list.
**/
public static <E> Node<E> listCopy(Node<E> source)
{
Node<E> copyHead;
Node<E> copyTail;
// Handle the special case of the empty list.
if (source == null)
return null;
// Make the first node for the newly created list.
copyHead = new Node<E>(source.data, null);
copyTail = copyHead;
// Make the rest of the nodes for the newly created list.
while (source.link != null)
{
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
// Return the head reference for the new list.
return copyHead;
}
/**
* Copy a list, returning both a head and tail reference for the copy.
* @param source
* the head of a linked list that will be copied (which may be
* an empty list in where source is null)
* @return
* The method has made a copy of the linked list starting at
* source. The return value is an
* array where the [0] element is a head reference for the copy and the [1]
* element is a tail reference for the copy.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for the new list.
**/
public static <E> Node<E>[ ] listCopyWithTail(Node<E> source)
{
Node<E> copyHead;
Node<E> copyTail;
//Node<E>[ ] answer = (Node<E>[]) new Object[2]; Causes ClassCastException!
Node<E>[ ] answer = createArray(null, null);
// Handle the special case of the empty list.
if (source == null)
return answer; // The answer has two null references .
// Make the first node for the newly created list.
copyHead = new Node<E>(source.data, null);
copyTail = copyHead;
// Make the rest of the nodes for the newly created list.
while (source.link != null)
{
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
// Return the head and tail references.
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* Compute the number of nodes in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list
* with a null head)
* @return
* the number of nodes in the list with the given head
* @note
* A wrong answer occurs for lists longer than Int.MAX_VALUE.
**/
public static <E> int listLength(Node<E> head)
{
Node<E> cursor;
int answer;
answer = 0;
for (cursor = head; cursor != null; cursor = cursor.link)
answer++;
return answer;
}
/**
* Copy part of a list, providing a head and tail reference for the new copy.
* @param start/end
* references to two nodes of a linked list
* @param copyHead/copyTail
* the method sets these to refer to the head and tail node of the new
* list that is created
* @precondition
* start and end are non-null references to nodes
* on the same linked list,
* with the start node at or before the end node.
* @return
* The method has made a copy of the part of a linked list, from the
* specified start node to the specified end node. The return value is an
* array where the [0] component is a head reference for the copy and the
* [1] component is a tail reference for the copy.
* @exception IllegalArgumentException
* Indicates that start and end do not satisfy
* the precondition.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for the new list.
**/
public static <E> Node<E>[ ] listPart(Node<E> start, Node<E> end)
{
Node<E> copyHead;
Node<E> copyTail;
Node<E> cursor;
//Node<E>[ ] answer = (Node<E>[]) new Object[2]; Causes ClassCastException!
Node<E>[ ] answer = createArray(null, null);
// Check for illegal null at start or end.
if (start == null)
throw new IllegalArgumentException("start is null");
if (end == null)
throw new IllegalArgumentException("end is null");
// Make the first node for the newly created list.
copyHead = new Node<E>(start.data, null);
copyTail = copyHead;
cursor = start;
// Make the rest of the nodes for the newly created list.
while (cursor != end)
{
cursor = cursor.link;
if (cursor == null)
throw new IllegalArgumentException
("end node was not found on the list");
copyTail.addNodeAfter(cursor.data);
copyTail = copyTail.link;
}
// Return the head and tail references
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* Find a node at a specified position in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list in
* which case the head is null)
* @param position
* a node number
* @precondition
* position > 0.
* @return
* The return value is a reference to the node at the specified position in
* the list. (The head node is position 1, the next node is position 2, and
* so on.) If there is no such position (because the list is too short),
* then the null reference is returned.
* @exception IllegalArgumentException
* Indicates that position is zero.
**/
public static <E> Node<E> listPosition(Node<E> head, int position)
{
Node<E> cursor;
int i;
if (position == 0)
throw new IllegalArgumentException("position is zero");
cursor = head;
for (i = 1; (i < position) && (cursor != null); i++)
cursor = cursor.link;
return cursor;
}
/**
* Search for a particular piece of data in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list in
* which case the head is null)
* @param target
* a target to search for
* @return
* The return value is a reference to the first node that contains the
* specified target. If the target is non-null, then the
* target.equals method is used to find such a node.
* The target may also be null, in which case the return value is a
* reference to the first node that contains a null reference for its
* data. If there is no node that contains the target, then the null
* reference is returned.
**/
public static <E> Node<E> listSearch(Node<E> head, E target)
{
Node<E> cursor;
if (target == null)
{ // Search for a node in which the data is the null reference.
for (cursor = head; cursor != null; cursor = cursor.link)
if (cursor.data == null)
return cursor;
}
else
{ // Search for a node that contains the non-null target.
for (cursor = head; cursor != null; cursor = cursor.link)
if (target.equals(cursor.data))
return cursor;
}
return null;
}
/**
* Modification method to remove the node after this node.
* @param - none
* @precondition
* This node must not be the tail node of the list.
* @postcondition
* The node after this node has been removed from the linked list.
* If there were further nodes after that one, they are still
* present on the list.
* @exception NullPointerException
* Indicates that this was the tail node of the list, so there is nothing
* after it to remove.
**/
public void removeNodeAfter( )
{
link = link.link;
}
/**
* Modification method to set the data in this node.
* @param newData
* the new data to place in this node
* @postcondition
* The data of this node has been set to newData.
* This data is allowed to be null.
**/
public void setData(E newData)
{
data = newData;
}
/**
* Modification method to set the link to the next node after this node.
* @param newLink
* a reference to the node that should appear after this node in the linked
* list (or the null reference if there is no node after this node)
* @postcondition
* The link to the node after this node has been set to newLink.
* Any other node (that used to be in this link) is no longer connected to
* this node.
**/
public void setLink(Node<E> newLink)
{
link = newLink;
}
/**
* Create an array of Node<E> objects. This is the only way that
* I've found to create such an array that doesn't cause a
* ClassCastException at run time. In the textbook, I used:
* // Node<E>[ ] answer = (Node<E>[]) new Object[2];
* but this approach now seems to fail. I'll keep looking for
* other solutions!
**/
private static <E> Node<E>[ ] createArray(Node<E>... nodes)
{
return nodes;
}
}
当您添加第一个节点时，link 它自身。虽然只有一个节点，但它会使它成为一个循环列表。
first -> first
然后，当您添加第二个节点时，您的代码将适用于循环列表中的保留节点。
first -> second -> first
后面的值就是第二个节点。
public void add(E item) {
Node cursor;
if (isEmpty( )) {
// Insert first item.
rear = new Node<E>(item, null);
rear.setLink(rear); // <=== add a link to itself to make it circular
}
else {
// Insert an item that is not the first.
rear.addNodeAfter(item);
rear = rear.getLink( );
}
manyNodes++;
}
当你想移除前端节点时。从后面取 link（这会给你前面），然后将后面的 link 设置为前面的 link（这会指向前面后面的那个）。
first -> second -> third -> first
变成
second -> third -> second
变成
third -> third
您需要注意检查列表是否只有一项。如果是，那么您可以通过将 rear 设置为 null 来清除列表。
public E remove() {
if (rear == null) {
// NoSuchElementException is from java.util and its constructor has no argument.
throw new NoSuchElementException("Queue underflow");
}
E answer = rear.getLink().getData();
if (rear.getLink() == rear) {
// this is the last item in the list
rear = null;
}
else {
// point rear to the one after front so that front is removed
rear.setLink(rear.getLink().getLink());
}
manyNodes--;
return answer;
}
Node class 中的静态方法假定 rear 的 link 为 null。循环列表不会出现这种情况。所以这些方法将一遍又一遍地围绕列表循环。所以如果你打算使用它们，请小心。
I am trying to implement number 6 in this picture
我主要是想制作一个循环 linked 列表，方法是制作一个从后节点到前节点的 link。但是在这个例子中，他们说不要使用对第一个节点的前端引用，所以我不确定如何在没有前端引用的情况下访问前端节点。
在添加和删除方法中，我只需要放一行代码
rear.setLink(front); 但是，如果没有前面的参考，我不知道该怎么做。这是我的代码，大部分是我们使用的教科书的修改代码
/*
* modified code from the book
*
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.NoSuchElementException;
//import edu.colorado.nodes.Node;
public class CircularLinkedList<E> implements Cloneable {
// File: LinkedQueue.java from the package edu.colorado.collections
// Complete documentation is available from the LinkedQueue link in:
// http://www.cs.colorado.edu/~main/docs/
// Invariant of the LinkedQueue class:
// 1. The number of items in the queue is stored in the instance variable
// manyNodes.
// 2. The items in the queue are stored in a linked list, with the front
// of the queue stored at the head node, and the rear of the queue at
// the final node.
// 3. For a non-empty queue, the instance variable front is the head
// reference of the linked list of items and the instance variable rear
// is the tail reference of the linked list. For an empty queue, both
// front and rear are the null reference.
private int manyNodes=0; //numberOf Nodes in list initialized to 0
//private Node<E> front;
private Node<E> rear;
/**
* Initialize an empty queue.
* <b>Postcondition:</b>
* This queue is empty.
**/
public <Node>CircularLinkedList( )
{
//front = null;
rear = null;
}
/**
* Put a new a new item in this queue.
* @param item
* the item to be pushed onto this queue
* <b>Postcondition:</b>
* The item has been pushed onto this queue.
* @exception OutOfMemoryError
* Indicates insufficient memory for increasing the queue's capacity.
* <b>Note:</b>
* An attempt to increase the capacity beyond
* <CODE>Integer.MAX_VALUE</CODE> will cause the queue to fail with an
* arithmetic overflow.
**/
public void add(E item)
{
Node cursor;
if (isEmpty( ))
{ // Insert first item.
rear = new Node<E>(item, null);
//rear = front;
}
else
{ // Insert an item that is not the first.
rear.addNodeAfter(item);
rear = rear.getLink( );
//for(cursor =rear; curs
// rear.setLink(CircularLinkedList.listposition(0)); //make link to front creating a circular linked List
}
manyNodes++;
}
/**
* Generate a copy of this queue.
* @return
* The return value is a copy of this queue. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to an <CODE>LinkedQueue</CODE> before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
**/
@SuppressWarnings("unchecked")
public CircularLinkedList<E> clone( )
{ // Clone a LinkedQueue<E>.
CircularLinkedList<E> answer;
Object[ ] cloneInfo;
try
{
answer = (CircularLinkedList<E>) super.clone( );
}
catch (CloneNotSupportedException e)
{
// This exception should not occur. But if it does, it would probably indicate a
// programming error that made super.clone unavailable. The most comon error
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
cloneInfo = Node.listCopyWithTail(rear);
// answer.front = (Node<E>) cloneInfo[0];
answer.rear = (Node<E>) cloneInfo[1];
return answer;
}
/**
* Determine whether this queue is empty.
* @return
* <CODE>true</CODE> if this queue is empty;
* <CODE>false</CODE> otherwise.
**/
public boolean isEmpty( )
{
return (manyNodes == 0);
}
/**
* Get the front item, removing it from this queue.
* <b>Precondition:</b>
* This queue is not empty.
* @return
* The return value is the front item of this queue, and the item has
* been removed.
* @exception NoSuchElementException
* Indicates that this queue is empty.
**/
public E remove( )
{
E answer;
if (manyNodes == 0)
// NoSuchElementException is from java.util and its constructor has no argument.
throw new NoSuchElementException("Queue underflow");
answer = rear.getData( );
// front = front.getLink( );
manyNodes--;
if (manyNodes == 0)
rear = null;
return answer;
//rear.setLink(front);
}
/**
* Accessor method to determine the number of itaems in this queue.
* @return
* the number of items in this queue
**/
public int size( )
{
return manyNodes;
}
public static void main(String[] args)
{
CircularLinkedList c1 = new CircularLinkedList();
c1.add(1);
c1.add(2);
c1.add(3);
c1.remove();
System.out.println("the data in the rear is " + c1.rear.getData());
//System.out.println("the data in the front is " + c1.front.getData());
// System.out.println("the data in node after rear is " + c1.rear.getLink().getData());
//System.out.println("this is because the rear links to the front making the Linked List circular");
}
}
下面是节点Class代码（不需要编辑）
class Node<E>
{
// Invariant of the Node class:
// 1. Each node has one reference to an E Object, stored in the instance
// variable data.
// 2. For the final node of a list, the link part is null.
// Otherwise, the link part is a reference to the
// next node of the list.
private E data;
private Node<E> link;
/**
* Initialize a node with a specified initial data and link to the next
* node. Note that the initialLink may be the null reference,
* which indicates that the new node has nothing after it.
* @param initialData
* the initial data of this new node
* @param initialLink
* a reference to the node after this new node--this reference may be null
* to indicate that there is no node after this new node.
* @postcondition
* This node contains the specified data and link to the next node.
**/
public Node(E initialData, Node<E> initialLink)
{
data = initialData;
link = initialLink;
}
/**
* Modification method to add a new node after this node.
* @param element
* the data to place in the new node
* @postcondition
* A new node has been created and placed after this node.
* The data for the new node is element. Any other nodes
* that used to be after this node are now after the new node.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for a new
* Node.
**/
public void addNodeAfter(E element)
{
link = new Node<E>(element, link);
}
/**
* Accessor method to get the data from this node.
* @param - none
* @return
* the data from this node
**/
public E getData( )
{
return data;
}
/**
* Accessor method to get a reference to the next node after this node.
* @param - none
* @return
* a reference to the node after this node (or the null reference if there
* is nothing after this node)
**/
public Node<E> getLink( )
{
return link;
}
/**
* Copy a list.
* @param source
* the head of a linked list that will be copied (which may be
* an empty list in where source is null)
* @return
* The method has made a copy of the linked list starting at
* source. The return value is the head reference for the
* copy.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for the new list.
**/
public static <E> Node<E> listCopy(Node<E> source)
{
Node<E> copyHead;
Node<E> copyTail;
// Handle the special case of the empty list.
if (source == null)
return null;
// Make the first node for the newly created list.
copyHead = new Node<E>(source.data, null);
copyTail = copyHead;
// Make the rest of the nodes for the newly created list.
while (source.link != null)
{
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
// Return the head reference for the new list.
return copyHead;
}
/**
* Copy a list, returning both a head and tail reference for the copy.
* @param source
* the head of a linked list that will be copied (which may be
* an empty list in where source is null)
* @return
* The method has made a copy of the linked list starting at
* source. The return value is an
* array where the [0] element is a head reference for the copy and the [1]
* element is a tail reference for the copy.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for the new list.
**/
public static <E> Node<E>[ ] listCopyWithTail(Node<E> source)
{
Node<E> copyHead;
Node<E> copyTail;
//Node<E>[ ] answer = (Node<E>[]) new Object[2]; Causes ClassCastException!
Node<E>[ ] answer = createArray(null, null);
// Handle the special case of the empty list.
if (source == null)
return answer; // The answer has two null references .
// Make the first node for the newly created list.
copyHead = new Node<E>(source.data, null);
copyTail = copyHead;
// Make the rest of the nodes for the newly created list.
while (source.link != null)
{
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
// Return the head and tail references.
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* Compute the number of nodes in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list
* with a null head)
* @return
* the number of nodes in the list with the given head
* @note
* A wrong answer occurs for lists longer than Int.MAX_VALUE.
**/
public static <E> int listLength(Node<E> head)
{
Node<E> cursor;
int answer;
answer = 0;
for (cursor = head; cursor != null; cursor = cursor.link)
answer++;
return answer;
}
/**
* Copy part of a list, providing a head and tail reference for the new copy.
* @param start/end
* references to two nodes of a linked list
* @param copyHead/copyTail
* the method sets these to refer to the head and tail node of the new
* list that is created
* @precondition
* start and end are non-null references to nodes
* on the same linked list,
* with the start node at or before the end node.
* @return
* The method has made a copy of the part of a linked list, from the
* specified start node to the specified end node. The return value is an
* array where the [0] component is a head reference for the copy and the
* [1] component is a tail reference for the copy.
* @exception IllegalArgumentException
* Indicates that start and end do not satisfy
* the precondition.
* @exception OutOfMemoryError
* Indicates that there is insufficient memory for the new list.
**/
public static <E> Node<E>[ ] listPart(Node<E> start, Node<E> end)
{
Node<E> copyHead;
Node<E> copyTail;
Node<E> cursor;
//Node<E>[ ] answer = (Node<E>[]) new Object[2]; Causes ClassCastException!
Node<E>[ ] answer = createArray(null, null);
// Check for illegal null at start or end.
if (start == null)
throw new IllegalArgumentException("start is null");
if (end == null)
throw new IllegalArgumentException("end is null");
// Make the first node for the newly created list.
copyHead = new Node<E>(start.data, null);
copyTail = copyHead;
cursor = start;
// Make the rest of the nodes for the newly created list.
while (cursor != end)
{
cursor = cursor.link;
if (cursor == null)
throw new IllegalArgumentException
("end node was not found on the list");
copyTail.addNodeAfter(cursor.data);
copyTail = copyTail.link;
}
// Return the head and tail references
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* Find a node at a specified position in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list in
* which case the head is null)
* @param position
* a node number
* @precondition
* position > 0.
* @return
* The return value is a reference to the node at the specified position in
* the list. (The head node is position 1, the next node is position 2, and
* so on.) If there is no such position (because the list is too short),
* then the null reference is returned.
* @exception IllegalArgumentException
* Indicates that position is zero.
**/
public static <E> Node<E> listPosition(Node<E> head, int position)
{
Node<E> cursor;
int i;
if (position == 0)
throw new IllegalArgumentException("position is zero");
cursor = head;
for (i = 1; (i < position) && (cursor != null); i++)
cursor = cursor.link;
return cursor;
}
/**
* Search for a particular piece of data in a linked list.
* @param head
* the head reference for a linked list (which may be an empty list in
* which case the head is null)
* @param target
* a target to search for
* @return
* The return value is a reference to the first node that contains the
* specified target. If the target is non-null, then the
* target.equals method is used to find such a node.
* The target may also be null, in which case the return value is a
* reference to the first node that contains a null reference for its
* data. If there is no node that contains the target, then the null
* reference is returned.
**/
public static <E> Node<E> listSearch(Node<E> head, E target)
{
Node<E> cursor;
if (target == null)
{ // Search for a node in which the data is the null reference.
for (cursor = head; cursor != null; cursor = cursor.link)
if (cursor.data == null)
return cursor;
}
else
{ // Search for a node that contains the non-null target.
for (cursor = head; cursor != null; cursor = cursor.link)
if (target.equals(cursor.data))
return cursor;
}
return null;
}
/**
* Modification method to remove the node after this node.
* @param - none
* @precondition
* This node must not be the tail node of the list.
* @postcondition
* The node after this node has been removed from the linked list.
* If there were further nodes after that one, they are still
* present on the list.
* @exception NullPointerException
* Indicates that this was the tail node of the list, so there is nothing
* after it to remove.
**/
public void removeNodeAfter( )
{
link = link.link;
}
/**
* Modification method to set the data in this node.
* @param newData
* the new data to place in this node
* @postcondition
* The data of this node has been set to newData.
* This data is allowed to be null.
**/
public void setData(E newData)
{
data = newData;
}
/**
* Modification method to set the link to the next node after this node.
* @param newLink
* a reference to the node that should appear after this node in the linked
* list (or the null reference if there is no node after this node)
* @postcondition
* The link to the node after this node has been set to newLink.
* Any other node (that used to be in this link) is no longer connected to
* this node.
**/
public void setLink(Node<E> newLink)
{
link = newLink;
}
/**
* Create an array of Node<E> objects. This is the only way that
* I've found to create such an array that doesn't cause a
* ClassCastException at run time. In the textbook, I used:
* // Node<E>[ ] answer = (Node<E>[]) new Object[2];
* but this approach now seems to fail. I'll keep looking for
* other solutions!
**/
private static <E> Node<E>[ ] createArray(Node<E>... nodes)
{
return nodes;
}
}
当您添加第一个节点时，link 它自身。虽然只有一个节点，但它会使它成为一个循环列表。
first -> first
然后，当您添加第二个节点时，您的代码将适用于循环列表中的保留节点。
first -> second -> first
后面的值就是第二个节点。
public void add(E item) {
Node cursor;
if (isEmpty( )) {
// Insert first item.
rear = new Node<E>(item, null);
rear.setLink(rear); // <=== add a link to itself to make it circular
}
else {
// Insert an item that is not the first.
rear.addNodeAfter(item);
rear = rear.getLink( );
}
manyNodes++;
}
当你想移除前端节点时。从后面取 link（这会给你前面），然后将后面的 link 设置为前面的 link（这会指向前面后面的那个）。
first -> second -> third -> first
变成
second -> third -> second
变成
third -> third
您需要注意检查列表是否只有一项。如果是，那么您可以通过将 rear 设置为 null 来清除列表。
public E remove() {
if (rear == null) {
// NoSuchElementException is from java.util and its constructor has no argument.
throw new NoSuchElementException("Queue underflow");
}
E answer = rear.getLink().getData();
if (rear.getLink() == rear) {
// this is the last item in the list
rear = null;
}
else {
// point rear to the one after front so that front is removed
rear.setLink(rear.getLink().getLink());
}
manyNodes--;
return answer;
}
Node class 中的静态方法假定 rear 的 link 为 null。循环列表不会出现这种情况。所以这些方法将一遍又一遍地围绕列表循环。所以如果你打算使用它们，请小心。