Java中的SLinkedList和Node [英] SLinkedList and Node in Java
问题描述
首先，是的，这是在课堂上的作业，但我对它的运作方式缺乏了解程度高于我想要的程度。
To start with, yes, this is for an assignment in class, but my lack of understanding on how it operates is higher than I want it to be.
我们获得了3个课程，分别如下：
We were given 3 classes, they are the following:
SLinkedList.java
SLinkedList.java
package chapter3.linkedList;
public class SLinkedList<V> {
// instance variables. Add the tail reference.
protected Node<V> head, tail;
protected long size;
// methods, empty list constructor first
public SLinkedList () {
head = null;
tail = null;
size = 0;
} // end constructor of a SLinkedList
// method to add nodes to the list. Storage space for the node
// is already allocated in the calling method
public void addFirst (Node<V> node) {
// set the tail only if this is the very first node
if (tail == null)
tail = node;
node.setNext (head); // make next of the new node refer to the head
head = node; // give head a new value
// change our size
size++;
} // end method addFirst
// addAfter - add new node after current node, checking to see if we are at the tail
public void addAfter (Node<V>currentNode, Node<V>newNode) {
if (currentNode == tail)
tail = newNode;
newNode.setNext (currentNode.getNext ());
currentNode.setNext (newNode);
// change our size
size++;
} // end method addAfter
// addLast - add new node after the tail node. Adapted from Code Fragment 3.15, p. 118.
// Mike Qualls
public void addLast (Node<V> node) {
node.setNext (null);
tail.setNext (node);
tail = node;
size++;
} // end method addLast
// methods to remove nodes from the list. (Unfortunately, with a single linked list
// there is no way to remove last. Need a previous reference to do that. (See
// Double Linked Lists and the code below.)
public Node<V> removeFirst () {
if (head == null)
System.err.println("Error: Attempt to remove from an empty list");
// save the one to return
Node<V> temp = head;
// do reference manipulation
head = head.getNext ();
temp.setNext(null);
size--;
return temp;
} // end method removeFirst
// remove the node at the end of the list. tail refers to this node, but
// since the list is single linked, there is no way to refer to the node
// before the tail node. Need to traverse the list.
public Node<V> removeLast () {
// // declare local variables/objects
Node<V> nodeBefore;
Node<V> nodeToRemove;
// make sure we have something to remove
if (size == 0)
System.err.println("Error: Attempt to remove fron an empty list");
// traverse through the list, getting a reference to the node before
// the trailer. Since there is no previous reference.
nodeBefore = getFirst ();
// potential error ?? See an analysis and drawing that indicates the number of iterations
// 9/21/10. size - 2 to account for the head and tail nodes. We want to refer to the one before the
// tail.
for (int count = 0; count < size - 2; count++)
nodeBefore = nodeBefore.getNext ();
// save the last node
nodeToRemove = tail;
// now, do the pointer manipulation
nodeBefore.setNext (null);
tail = nodeBefore;
size--;
return nodeToRemove;
} // end method removeLast
// method remove. Remove a known node from the list. No need to search or return a value. This method
// makes use of a 'before' reference in order to allow list manipulation.
public void remove (Node<V> nodeToRemove) {
// declare local variables/references
Node<V> nodeBefore, currentNode;
// make sure we have something to remove
if (size == 0)
System.err.println("Error: Attempt to remove fron an empty list");
// starting at the beginning check for removal
currentNode = getFirst ();
if (currentNode == nodeToRemove)
removeFirst ();
currentNode = getLast ();
if (currentNode == nodeToRemove)
removeLast ();
// we've already check two nodes, check the rest
if (size - 2 > 0) {
nodeBefore = getFirst ();
currentNode = getFirst ().getNext ();
for (int count = 0; count < size - 2; count++) {
if (currentNode == nodeToRemove) {
// remove current node
nodeBefore.setNext (currentNode.getNext ());
size--;
break;
} // end if node found
// change references
nodeBefore = currentNode;
currentNode = currentNode.getNext ();
} // end loop to process elements
} // end if size - 2 > 0
} // end method remove
// the gets to return the head and/or tail nodes and size of the list
public Node<V> getFirst () { return head; }
public Node<V> getLast () { return tail; }
public long getSize () { return size; }
} // end class SLinkedList
Node.java
Node.java
package chapter3.linkedList;
package chapter3.linkedList;
public class Node<V> {
// instance variables
private V element;
private Node<V> next;
// methods, constructor first
public Node () {
this (null, null); // call the constructor with two args
} // end no argument constructor
public Node (V element, Node<V> next) {
this.element = element;
this.next = next;
} // end constructor with arguments
// set/get methods
public V getElement () { return element; }
public Node<V> getNext () { return next; }
public void setElement (V element) { this.element = element; }
public void setNext (Node<V> next) { this.next = next; }
} // end class Node
和GameEntry.java
and GameEntry.java
package Project_1;
public class GameEntry
{
protected String name; // name of the person earning this score
protected int score; // the score value
/** Constructor to create a game entry */
public GameEntry(String name, int score)
{
this.name = name;
this.score = score;
}
/** Retrieves the name field */
public String getName()
{
return name;
}
/** Retrieves the score field */
public int getScore()
{
return score;
}
/** Returns a string representation of this entry */
public String toString()
{
return "(" + name + ", " + score + ")";
}
}
我花了3天几个小时听他的讲座，阅读文本（数据结构和算法第5版），并浏览互联网论坛和youtube视频，但我似乎无法理解如何利用节点/ slinkedlist类。
I've spent the past 3 hours listening to his lecture, reading through the text (Data Structures and Algorithms 5th Edition), and looking through internet forums and youtube videos, but I can't seem to grasp any understanding of how to utilize the node/slinkedlist class.
分配的对象是编写一个维护前10个分数的类或游戏应用程序，实现添加和删除方法，但使用单个链表而不是数组。
The object of the assignment is "Write a class that maintains the top 10 scores or a game application, implementing the add and remove methods, but using a single linked list instead of an array.
我不希望有人为我这样做，但我确实想知道如何制作链表。我知道这些并不难，但是使用这些代码执行它们已经变得非常困难，任何帮助都会非常感激。
I don't want someone to do this for me, but I do want to know how to make the linked list. I know these are NOT that hard, but doing them with this code he's given has become painfully difficult, any help would be really appreciated.
提前谢谢。
编辑：
我的主要功能：ScoresTest.java
My main function: ScoresTest.java
package Project_1;
public class ScoresTest {
/**
* @param args
*/
public static void main(String[] args)
{
GameEntry entry;
Scores highScores = new Scores();
entry = new GameEntry("Anna", 600);
highScores.add(entry);
entry = new GameEntry("Paul", 720);
highScores.add(entry);
System.out.println("The Original High Scores");
System.out.println(highScores);
entry = new GameEntry("Jill", 1150);
highScores.add(entry);
System.out.println("Scores after adding Jill");
System.out.println(highScores);
}
}
这大部分是准确的它应该如何最终看起来，但是这一切使得这项工作让我失望......好吧......所有涉及上述3个类的事情，如果它们不是没有太多的因素，我可以做到这一点问题，它们是导致我空白的原因。
This is for the most part exactly how it should end up looking, but it's everything that makes this work that's throwing me off...well...everything dealing with the 3 classes mentioned above, I could do this if they weren't a factor without too much of an issue, they are what's causing my blank.
推荐答案
这是一个骷髅，没有为你做太多，这至少可以告诉你你在上面的评论中到目前为止：
Here is a skeleton, without doing much for you this at least talks you through what you have so far in the comments above:
public class ScoreDriver
{
public static void main(String[] args)
{
SLinkedList<GameEntry> sll = new SlinkedList<GameEntry>();
}
}
一旦你在eclipse中拥有它，自动完成将带你走得很远。如果您以前从未见过它们，那么使用泛型实例化链表类可能会很奇怪。专注于SLinkedList虽然它有很多实用功能，但不要过早担心Node。
Once you have this in eclipse, auto-complete will take you pretty far. Instantiating the linked list class with generics could be odd if you've never seen them before. Focus, on SLinkedList though it has a lot of utility for what you want to do, don't worry about Node too much upfront.
这篇关于Java中的SLinkedList和Node的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
