добавление и удаление из односвязного списка

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 + "\n"; 
    }

}

ПРАВКА РЕДАКТИРОВАНИЯ Iсоздал драйвер с именем Scores.java, в нем пока все, что у меня есть, ** я добавил то, что мне кажется необходимым для занятий, но, вероятно, я ошибаюсь:

package Project_1;

import chapter3.linkedList.*;

import java.util.*;


/** Class for storing high scores in an array in non-decreasing order. */
public class Scores 
{

    //add function
    public SLinkedList<GameEntry> add(GameEntry rank, SLinkedList<GameEntry> scores)
    {
        Node<GameEntry> currentNode = scores.getFirst();
        Node<GameEntry> nextNode = null;
        Node<GameEntry> previousNode = null;
        Node<GameEntry> newNode = new Node<GameEntry>();
        newNode.setElement(rank);

        if(scores.getSize() == 0)
        {
            scores.addFirst(newNode);
        }
        else
        {
            while(currentNode != null)
            {               
                nextNode = currentNode.getNext();
                if(nextNode == null)
                {
                    scores.addLast(newNode);
                }
                else
                {
                    scores.addAfter(currentNode, newNode);
                    break;
                }               
            previousNode = currentNode;
            currentNode = currentNode.getNext();
            }
        }
        return scores;
    }

    //remove function
    public void remove(int i)
    {

    }

    //print function
    /*gameenter printing; 
printing=node.Getelement;           //pseudo code for making it work right
print(printing.getscore) 
print(print.getname) 
*/
    public void print(SLinkedList<GameEntry> scores)
    {
        Node<GameEntry> currentNode = scores.getFirst();        
        GameEntry currentEntry = currentNode.getElement();      
        System.out.printf("[");
        for(int i = 0; i < scores.getSize(); i++)
        {
                System.out.printf(", %s", currentEntry.toString());
                currentNode = currentNode.getNext();
                currentEntry = currentNode.getElement();
        }
        System.out.println("]");
    }
}

У меня есть тестдрайвер под названием ScoresTest.java, который я почти полностью заполнил:

пакет Project_1;

import chapter3.linkedList.SLinkedList;

 public class ScoresTest {
    /**
     * @param args
     */

    public static void main(String[] args) 
    {
        SLinkedList<GameEntry> highScores = new SLinkedList<GameEntry>();  //Linked List for Game Entry
        GameEntry entry;
        Scores rank = new Scores();     
        entry = new GameEntry("Flanders", 681);     
        highScores = rank.add(entry, highScores);
        entry = new GameEntry("Krusty", 324);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Otto", 438);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Bart", 875);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Homer", 12);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Lisa", 506);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Maggie", 980);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Apoo", 648);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Smithers", 150);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Burns", 152);
        highScores = rank.add(entry, highScores); 
        System.out.println("The Original High Scores");
        rank.print(highScores);

        entry = new GameEntry("Moe", 895);
        highScores = rank.add(entry, highScores);
        System.out.println("Scores after adding Moe");
        rank.print(highScores);

        //highScores = rank.remove(4);
        System.out.println("Scores after removing Apoo");
        rank.print(highScores);
    }
}

Это полностью закончено, довольноуверен, что мне нечего добавить.

Я нЯ не ищу, чтобы кто-то отвечал за меня, но я понятия не имею, с чего начать или как сделать функцию добавления или удаления.Это промежуточный курс, книга ничего не делает для объяснения связанных списков (продолжайте и посмотрите сами, если вы мне не верите, текст называется Datastructures and Algorithms in Java, 5-е издание).Он показывает, как сделать это с помощью массива довольно легко ... который отлично работает для связанного списка, но, очевидно, учитель не хочет, чтобы мы делали это таким образом, так что, к сожалению, я теперь совершенно потерян, как это сделать.

Я попытался посмотреть ответы других людей здесь и в Google, и до сих пор ничего не щелкнуло и не имело никакого смысла вообще, я просто не могу понять, как это работает, и объяснение и пример учителя были толькочтобы рисовать прямоугольники на доске, я никогда не видел функции сортировки, добавления или удаления, закодированной для связанного списка ... не могу знать, чему меня не учили или не могу найти.

Любая помощь очень ценится, и спасибо заранее!

РЕДАКТИРОВАТЬ

Я посмотрел на импорт java.util. *;и команды в нем для связанных списков, они кажутся до боли легкими.чтобы удалить, я бы просто использовал list.sublist (i, i) .clear ();и значение, которое я хочу удалить, удалено, супер просто, кажется, что я просто пытаюсь использовать slinkedlist.java и node.java, я просто не могу следовать им каким-либо образом.Я полагаю, что учитель действительно написал их, и я пытался попросить его помощи, оставался 2 часа после урока, пытаясь получить от него какое-либо понимание, и, как вы можете видеть, это совсем не помогло.Еще раз спасибо за помощь!

РЕДАКТИРОВАТЬ

Я также прошу прощения, если это кажется расплывчатым, но у меня нет конкретной точки, где мое замешательство кажетсясвязанный, я понимаю связанные списки, если мы говорим о java.util.linkedList; но, поскольку я использую то, что мне дали в этих обстоятельствах, я вообще не могу следовать логике, оставляя меня совершенно потерянным ине знаете, с чего начать.

Answer 1

В псевдокоде (обратите внимание, я не включаю проверку границ и т. Д., Просто логику)

Чтобы добавить узел в начало списка:

newNode->nextNode = startNode
startNode = newNode

Чтобы добавить к определенному индексу:

index = 0
currentNode = startNode

// find the node in the list. here you will need to do all kinds of bound checking
while index is less than position
    currentNode = currentNode.nextNode  // move your node pointer to the position
    increment index

// so here we basically insert the new node into the list. what needs to happen is
// to NOT break the list by forgetting the node after the current node. this is why
// we first set the new nodes' next one, to the current nodes' (the one already in
// the list) next node. this way, we still have all the information we need. then,
// when we set the current nodes' next node to the new node, we essentially "break"
// the link and "repair" it by adding the new link.

newNode.nextNode = currentNode.nextNode // some more bound checking required
currentNode.nextNode = newNode

Чтобы удалить из определенного индекса:

index = 0
delNode = startNode

// find the node in the list. here you will need to do all kinds of bound checking
while index is less than (position - 1)
    delNode = delNode.nextNode  // move your node pointer to the position
    increment index

delNode.nextNode = delNode.nextNode.nextNode

// that's it. by setting the node's (before the one you whish to delete)
// next node to the node AFTER the one you want to delete, you basically
// "skip" over that node. since it is no longer referenced, the garbage
// collector will take care of the rest. if you wish to return that node
// you can do it quite easily by remembering it.

storeNode = delNode.nextNode                 // some more bound checking required
delNode.nextNode = delNode.nextNode.nextNode // some more bound checking required

// now you still have a reference to the deleted node in storeNode

---

UPDATE

ОК, поэтому, если я правильно понимаю, вам нужно создать связанный список, в котором результаты сохраняются в порядке возрастания. Насколько я вижу, весь связанный список был реализован для вас, вам просто нужно использовать предоставленные классы и добавить логику в Scores.java, чтобы сохранить список отсортированным.

Во-первых, я вижу, что ваши узлы несопоставимы. Если вам вообще разрешено изменять данный вам источник, я бы посоветовал им реализовать Comparable<Node>, а также переопределить equals(Object o), чтобы у вас была логика для сравнения. Два узла могут содержать один и тот же элемент, но это не значит, что они равны.

Обратите внимание на изменение сигнатур метода!

//add function
public void add(Node<GameEntry> score) {
    // adding is where you now want to keep everything sorted. so I highly
    // recommend that you implement `Comparable` as I mentioned above. if not,
    // you have to put the logic in here.

    Node<GameEntry> currentNode = highScored.getFirst();
    Node<GameEntry> prevNode = null;

    // if the list is empty, or the new node must go in before the head,
    // simply add it as the head.
    if (highScores.size() == 0 || score.compareTo(currentNode) < 0) {
        highScores.addFirst(score);
    }

    // search for the position of the new node. while the node has a higher score
    // than the current node, we need to continue on so we can place it in the
    // correct place.
    while (currentNode != null && currentNode.compareTo(score) > 0) {
        prevNode = currentNode;
        currentNode = currentNode.getNext();
    }

    // if the currentNode is null, it means it is the highest score, so
    // we can simply add it to the end
    if (currentNode == null) {
        highScores.addLast(score);
    } else {
        // otherwise just add it after the correct node
        highScores.addAfter(prevNode, score);
    }
}


//remove function
public void remove(Node<GameEntry> score) {
    // removing an element should be as described above. if you keep
    // your list sorted during the ADD method, removing any element
    // should not break the order.

    // find the element - removal from a linked list is O(n),
    // since we need to know what the element BEFORE the one
    // is that you want to remove. assuming you have implemented
    // the equals method to check equality of nodes:

    Node<GameEntry> currentNode = highScores.getFirst();
    Node<GameEntry> prevNode = null;
    while (currentNode != null && !currentNode.equals(score)) {
        prevNode = currentNode;
        currentNode = currentNode.getNext();
    }

    // if currentNode is null, the node we wanted to remove was not
    // in the list.
    if (currentNode == null) {
        System.out.println("Node not found");
        return;
    }

    // now, we need to check if there is a node after the one we want
    // to remove.
    if (prevNode.getNext().getNext() != null) {
        // if there is, we follow the logic from the pseudo code
        prevNode.setNext(prev.getNext().getNext());
    } else {
        // if not, we only need to remove the last entry (since the
        // one we want to remove is the last one)
        highScores.removeLast();
    }
}

ВАЖНО

Пожалуйста, просто проверьте здесь логику. Я сделал это очень быстро без IDE, так как сейчас я не за компьютером разработки. Если кто-то обнаружит какие-либо проблемы, пожалуйста, оставьте комментарий, и я исправлю его.

Если это не совсем то, что вы спросили (ваш вопрос немного расплывчатый), дайте мне знать.

---

ОБНОВЛЕНИЕ 2

Читайте о Comparator с здесь , здесь и здесь .