Java 中的 SLinkedList 和节点

SLinkedList and Node in Java

提问by Soully

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.

首先，是的，这是课堂作业，但我对它的运作方式缺乏了解，这超出了我的预期。

We were given 3 classes, they are the following:

我们给了 3 个班级，它们如下：

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

节点.java

package chapter3.linkedList;

包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

and GameEntry.java

和 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 + ")"; 
    }

}

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.

我花了 3 个小时听他的讲座，通读课文（数据结构和算法第 5 版），并浏览互联网论坛和 YouTube 视频，但我似乎无法理解如何利用节点/链表类。

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.

作业的对象是“编写一个维护前 10 名分数的类或一个游戏应用程序，实现 add 和 remove 方法，但使用单个链表而不是数组。

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.

我不希望有人为我做这件事，但我确实想知道如何制作链表。我知道这些并不难，但是用他给出的这段代码来做这些事情变得非常困难，任何帮助都将不胜感激。

Thank you in advance.

先感谢您。

Edit:

编辑：

My main function: ScoresTest.java

我的主要功能：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);
    }

}

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.

这在很大程度上正是它最终看起来的样子，但正是让这项工作让我失望的一切......好吧......所有处理上述 3 个类的事情，如果他们不是，我可以做到这一点一个没有太大问题的因素，它们是导致我空白的原因。

回答by Mike K.

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>();
  }
}

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.

一旦你在 eclipse 中拥有了这个，自动完成将带你走得很远。如果您以前从未见过，用泛型实例化链表类可能会很奇怪。专注于 SLinkedList，尽管它对您想做的事情有很多实用程序，但不要预先担心 Node。