Java 中的 SLinkedList 和 Node

Question

首先，是的，这是课堂作业，但我对它的运作方式缺乏了解，这比我想要的要严重。

我们得到了 3 个类，它们如下：

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

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

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 视频，但我似乎无法掌握任何理解如何使用节点/链接列表类。

作业的目标是“编写一个维护前 10 名分数的类或游戏应用程序，实现添加和删除方法，但使用单个链表而不是数组。

我不希望有人为我做这件事，但我确实想知道如何制作链接列表，我知道这些并不难，但是用他给出的代码来做它们已经变得非常困难，任何帮助都会非常感谢

。

编辑：

我的 主要功能：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 个类的事情，如果它们不是一个因素，我可以这样做没有太大问题，它们就是导致我空白的原因。

Answer 1

这是一个框架，没有为您做太多事情，但至少可以告诉您到目前为止在上面的评论中所了解的内容：

public class ScoreDriver
{

  public static void main(String[] args)
  {
    SLinkedList<GameEntry> sll = new SlinkedList<GameEntry>();
  }
}

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