java - 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

节点.java

封装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 视频，但我似乎无法理解如何使用 node/slinkedlist 类。

作业的对象是“编写一个维护前 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 太前期。