реализация связанного списка Java

Question

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

Вход

anything
one
two
three

исключение:

Exception in thread "main" java.lang.NullPointerException
    at LinkedList.remove(LinkedList.java:28)
    at Main.main(Main.java:29)

Классы: класс связанного списка

public class LinkedList {

    // fields
    private Node head;
    private Node last;
    private int size = 0;

    // constructor, used when the class is first called
    public LinkedList() {
        head = last = new Node(null);
    }

    // add method
    public void add(String s) {
        last.setNext(new Node(s));
        last = last.getNext();
        size++;
    }

    // remove method, if it returns false then the specified index element doens not exist
    // otherwise will return true
    public boolean remove(String data) {
        Node current = head;
        last = null;
        while(current != null) {
            if(current.getData().equals(data)) {
                current = current.getNext();
                if(last == null) {
                    last = current;
                }else {
                    last.getNext().setNext(current);
                    size--;
                    return true;
                }
            }else {
                last = current;
                current = current.getNext();
            }
        }
        return false;
    }
    //will return the size of the list - will return -1 if list is empty
    public int size() {
        return size;
    }

    // will check if the list is empty or not
    public boolean isEmpty() {
        return true;
    }

    // @param (index) will get the data at specified index
    public String getData(int index) {

        if(index <= 0) {
            return null;
        }

        Node current = head.getNext();
        for(int i = 1;i < index;i++) {
            if(current.getNext() == null) {
                return null;
            }
            current = current.getNext();
        }

        return current.getData();
    }

    //@param will check if the arguement passed is in the list
    // will return true if the list contains arg otherwise false
    public boolean contains(String s) {
        for(int i = 1;i<=size();i++) {
            if(getData(i).equals(s)) {
                return true;
            }
        }
        return false;
    }

    //@return contents of the list - recursively 
    public String toString() {
        Node current = head.getNext();
        String output = "[";
        while(current != null) {
            output += current.getData()+",";
            current = current.getNext();
        }
        return output+"]";
    }

    //@return first node
    public Node getHead() {
        return head;
    }

    // @return (recursively) list
    public void print(Node n) {
        if(n == null) {
            return;
        }else {
            System.out.println(n.getData());
            print(n.getNext());
        }
    }
}

Main

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException{
        LinkedList list = new LinkedList(); // declaring main linked list
        LinkedList b_List = new LinkedList(); // declaring the backup list

        String input = null;
        // getting input from user, will stop when user has entered 'fin'
        while(!(input = br.readLine()).equals("fin")) {
            list.add(input); // adding to main list
            b_List.add(input);
        }

        list.print(list.getHead().getNext());

        System.out.println("Input Complete.");
        if(list.size() == 1) {
            System.out.println("You have entered only one name. He/She is the survior");
        }else {
            System.out.println("Enter the name(s) would like to remove: ");
            while(b_List.size() != 1) {
                String toRemove = br.readLine();
                b_List.remove(toRemove);
            }
        }
        System.out.println("The contestants were: ");
        list.print(list.getHead().getNext());
    }
}

узел

public class Node {

    // Fields
    private String data;
    private Node next;

    // constructor
    public Node(String data) {
        this(data,null);
    }

    // constructor two with Node parameter
    public Node(String data, Node node) {
        this.data = data;
        next = node;
    }

    /**
     * Methods below return information about fields within class
     * */

    // @return the data
    public String getData() {
        return data;
    }

    // @param String data to this.data
    public void setData(String data) {
        this.data = data;
    }

    // @return next
    public Node getNext() {
        return next;
    }
    // @param Node next set to this.next
    public void setNext(Node next) {
        this.next = next;
    }

}

Answer 1

Во-первых, ваша голова - это просто маркер перед первым, поэтому вы не должны запускать проверку удаления из нее.

Во-вторых, ваш remove метод завершится неудачно, если данные узла null

В-третьих, ваша реализация все равно не работает из-за last.getNext().setNext(current) - она ​​не будет связывать предыдущий узел со следующим, она будет связывать текущий со следующим (то есть ничего не будет делать)

Четвертый - это все ещене удается удалить первый элемент из-за загадочных операций с last ...

Правильная реализация remove будет выглядеть примерно так:

public boolean remove(String data){
    Node current = head.getNext();
    Node previous = null;
    while (current != null) {
        String dataOld = current.getData();
        if ((dataOld == null && data == null) || (dataOld != null && dataOld.equals(data))) {
            Node afterRemoved = current.getNext();
            if (previous == null) {
                head.setNext(afterRemoved);
            } else {
                previous.setNext(afterRemoved);
            }
            if (afterRemoved.getNext() == null) {
                last = afterRemoved;
            }
            size--;
            return true;
        } else {
            previous = current;
            current = current.getNext();
        }
    }
    return false;
}

Answer 2

Рассмотрим еще одну возможную реализацию рабочего нерекурсивного связанного списка с общим заполнителем T.Он работает «из коробки», а код более прост:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList<T> implements Iterable<T> {
    private Node first;
    private Node last;
    private int N;

    public LinkedList() {
        first = null;
        last = null;
        N = 0;
    }

    public void add(T item) {
        if (item == null) { throw new NullPointerException("Null object!"); }
        if (!isEmpty()) {
            Node prev = last;
            last = new Node(item, null);
            prev.next = last;
        }
        else {
            last = new Node(item, null);
            first = last;
        }
        N++;
    }

    public boolean remove(T item) {
        if (isEmpty()) { throw new IllegalStateException("Empty list!"); }
        boolean result = false;
        Node prev = first;
        Node curr = first;
        while (curr.next != null || curr == last) {
            if (curr.data.equals(item)) {
                // remove the last remaining element
                if (N == 1) { first = null; last = null; }
                // remove first element
                else if (curr.equals(first)) { first = first.next; }
                // remove last element
                else if (curr.equals(last)) { last = prev; last.next = null; }
                // remove element
                else { prev.next = curr.next; }
                N--;
                result = true;
                break;
            }
            prev = curr;
            curr = prev.next;
        }
        return result;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private class Node {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public Iterator<T> iterator() { return new LinkedListIterator(); }

    private class LinkedListIterator implements Iterator<T> {
        private Node current = first;

        public T next() {
            if (!hasNext()) { throw new NoSuchElementException(); }
            T item = current.data;
            current = current.next;
            return item;
        }

        public boolean hasNext() { return current != null; }

        public void remove() { throw new UnsupportedOperationException(); }
    }

    @Override public String toString() {
        StringBuilder s = new StringBuilder();
        for (T item : this)
            s.append(item + " ");
        return s.toString();
    }

    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        while(!StdIn.isEmpty()) {
            String input = StdIn.readString();
            if (input.equals("print")) { StdOut.println(list.toString()); continue; }
            if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
            if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
            break;
        }
    }
}

. Для получения дополнительных примеров LinkedList вы можете проверить статью .

Answer 3

Вот полная реализация связанного списка

включая вставку, удаление, поиск, реверсирование, обмен, изменение размера, отображение и различные важные операции связанного списка

import java.util.NoSuchElementException;
import java.util.Scanner;

class Node<T> {

    public Node<T> next;
    public T data;

    public Node() {

    }

    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node [next=" + next + ", data=" + data + "]";
    }
}

class LinkedList<T> {

    Node<T> start = null;
    Node<T> end = null;

    public void insertAtStart(T data) {
        Node<T> nptr = new Node<T>(data, null);
        if (empty()) {
            start = nptr;
            end = start;
        } else {
            nptr.next = start;
            start = nptr;
        }
        display();
    }

    public void insertAtEnd(T data) {
        Node<T> nptr = new Node<T>(data, null);
        if (empty()) {
            insertAtStart(data);
            return;
        } else {
            end.next = nptr;
            end = nptr;
        }
        display();
    }

    public void insertAtPosition(int position, T data) {
        if (position != 1 && empty())
            throw new IllegalArgumentException("Empty");
        if (position == 1) {
            insertAtStart(data);
            return;
        }

        Node<T> nptr = new Node<T>(data, null);
        if (position == size()) {

            Node<T> startPtr = start;
            Node<T> endPtr = startPtr;
            while (startPtr.next != null) {
                endPtr = startPtr;
                startPtr = startPtr.next;
            }
            endPtr.next = nptr;
            nptr.next = end;
        } else {
            position -= 1;
            Node<T> startPtr = start;
            for (int i = 1; i < size(); i++) {
                if (i == position) {
                    Node<T> temp = startPtr.next;
                    startPtr.next = nptr;
                    nptr.next = temp;
                }
                startPtr = startPtr.next;
            }
        }
        display();
    }

    public void delete(int position) {

        if (empty())
            throw new IllegalArgumentException("Empty");

        if (position == 1) {
            start = start.next;
        } else if (position == size()) {
            Node<T> startPtr = start;
            Node<T> endPtr = start;
            while (startPtr.next != null) {
                endPtr = startPtr;
                startPtr = startPtr.next;
            }
            endPtr.next = null;
            end = endPtr;
        } else {
            position -= 1;
            Node<T> startPtr = start;
            for (int i = 1; i <= position; i++) {
                if (i == position) {
                    Node<T> temp = startPtr.next.next;
                    startPtr.next = temp;
                }
                startPtr = startPtr.next;
            }
        }
        display();
    }

    public int index(T data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        return index(start, data, 0);
    }

    private int index(Node<T> link, T data, int index) {
        if (link != null) {
            if (link.data == data) {
                return index;
            }
            return index(link.next, data, ++index);
        }
        return -1;
    }

    public void replace(int position, T data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (position == 1)
            start.data = data;
        else if (position == size())
            end.data = data;
        else {
            Node<T> startPtr = start;
            for (int i = 1; i <= position; i++) {
                if (i == position)
                    startPtr.data = data;
                startPtr = startPtr.next;
            }
        }
        display();
    }

    public void replaceRecursively(int position, T data) {
        replaceRecursively(start, position, data, 1);
        display();
    }

    private void replaceRecursively(Node<T> link, int position, T data, int count) {
        if (link != null) {
            if (count == position) {
                link.data = data;
                return;
            }
            replaceRecursively(link.next, position, data, ++count);
        }
    }

    public T middle() {
        if (empty())
            throw new NoSuchElementException("Empty");
        Node<T> slowPtr = start;
        Node<T> fastPtr = start;
        while (fastPtr != null && fastPtr.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        return slowPtr.data;
    }

    public int occurence(T data) {
        if (empty())
            throw new NoSuchElementException("Empty");
        return occurence(start, data, 0);
    }

    private int occurence(Node<T> link, T data, int occurence) {
        if (link != null) {
            if (link.data == data)
                ++occurence;
            return occurence(link.next, data, occurence);
        }
        return occurence;
    }

    public void reverseRecusively() {
        reverseRecusively(start);
        swapLink();
        display();
    }

    private Node<T> reverseRecusively(Node<T> link) {
        if (link == null || link.next == null)
            return link;
        Node<T> nextLink = link.next;
        link.next = null;
        Node<T> revrseList = reverseRecusively(nextLink);
        nextLink.next = link;
        return revrseList;
    }

    public void reverse() {
        if (empty())
            throw new NoSuchElementException("Empty");
        Node<T> prevLink = null;
        Node<T> currentLink = start;
        Node<T> nextLink = null;
        while (currentLink != null) {
            nextLink = currentLink.next;
            currentLink.next = prevLink;
            prevLink = currentLink;
            currentLink = nextLink;
        }
        swapLink();
        display();
    }

    private void swapLink() {
        Node<T> temp = start;
        start = end;
        end = temp;
    }

    public void swapNode(T dataOne, T dataTwo) {
        if (dataOne == dataTwo)
            throw new IllegalArgumentException("Can't swap " + dataOne + " and " + dataTwo + " both are same");
        boolean foundDataOne = false;
        boolean foundDataTwo = false;

        Node<T> dataOnePtr = start;
        Node<T> dataOnePrevPtr = start;
        while (dataOnePtr.next != null && dataOnePtr.data != dataOne) {
            dataOnePrevPtr = dataOnePtr;
            dataOnePtr = dataOnePtr.next;
        }

        Node<T> dataTwoPtr = start;
        Node<T> dataTwoPrevPtr = start;
        while (dataTwoPtr.next != null && dataTwoPtr.data != dataTwo) {
            dataTwoPrevPtr = dataTwoPtr;
            dataTwoPtr = dataTwoPtr.next;
        }

        if (dataOnePtr != null && dataOnePtr.data == dataOne)
            foundDataOne = true;

        if (dataTwoPtr != null && dataTwoPtr.data == dataTwo)
            foundDataTwo = true;

        if (foundDataOne && foundDataTwo) {

            if (dataOnePtr == start)
                start = dataTwoPtr;
            else if (dataTwoPtr == start)
                start = dataOnePtr;

            if (dataTwoPtr == end)
                end = dataOnePtr;
            else if (dataOnePtr == end)
                end = dataTwoPtr;

            Node<T> tempDataOnePtr = dataOnePtr.next;
            Node<T> tempDataTwoPtr = dataTwoPtr.next;

            dataOnePrevPtr.next = dataTwoPtr;
            dataTwoPtr.next = tempDataOnePtr;
            dataTwoPrevPtr.next = dataOnePtr;
            dataOnePtr.next = tempDataTwoPtr;

            if (dataOnePtr == dataTwoPrevPtr) {
                dataTwoPtr.next = dataOnePtr;
                dataOnePtr.next = tempDataTwoPtr;
            } else if (dataTwoPtr == dataOnePrevPtr) {
                dataOnePtr.next = dataTwoPtr;
                dataTwoPtr.next = tempDataOnePtr;
            }

        } else
            throw new NoSuchElementException("Either " + dataOne + " or " + dataTwo + " not in the list");
        display();
    }

    public int size() {
        return size(start, 0);
    }

    private int size(Node<T> link, int i) {
        if (link == null)
            return 0;
        else {
            int count = 1;
            count += size(link.next, 0);
            return count;
        }
    }

    public void printNthNodeFromLast(int n) {

        if (empty())
            throw new NoSuchElementException("Empty");

        Node<T> main_ptr = start;
        Node<T> ref_ptr = start;

        int count = 0;
        while (count < n) {
            if (ref_ptr == null) {
                System.out.println(n + " is greater than the no of nodes in the list");
                return;
            }
            ref_ptr = ref_ptr.next;
            count++;
        }

        while (ref_ptr != null) {
            main_ptr = main_ptr.next;
            ref_ptr = ref_ptr.next;
        }

        System.out.println("Node no " + n + " from the last is " + main_ptr.data);

    }

    public void display() {
        if (empty())
            throw new NoSuchElementException("Empty");
        display(start);
    }

    private void display(Node<T> link) {
        if (link != null) {
            System.out.print(link.data + " ");
            display(link.next);
        }
    }

    public boolean empty() {
        return start == null;
    }

}

public class LinkedListTest {

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        boolean yes = true;
        Scanner scanner = new Scanner(System.in);
        do {
            System.out.println("\n1. Insert At Start");
            System.out.println("2. Insert At End");
            System.out.println("3. Insert at Position");
            System.out.println("4. Delete");
            System.out.println("5. Display");
            System.out.println("6. Empty status");
            System.out.println("7. Get Size");
            System.out.println("8. Get Index of the Item");
            System.out.println("9. Replace data at given position");
            System.out.println("10. Replace data at given position recusively");
            System.out.println("11. Get Middle Element");
            System.out.println("12. Get Occurence");
            System.out.println("13. Reverse Recusively");
            System.out.println("14. Reverse");
            System.out.println("15. Swap the nodes");
            System.out.println("16. Nth Node from last");
            System.out.println("\nEnter your choice");
            int choice = scanner.nextInt();

            switch (choice) {
            case 1:
                try {
                    System.out.println("Enter the item");
                    linkedList.insertAtStart(scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 2:
                try {
                    System.out.println("Enter the item");
                    linkedList.insertAtEnd(scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 3:
                try {
                    System.out.println("Enter the position");
                    int position = scanner.nextInt();
                    if (position < 1 || position > linkedList.size()) {
                        System.out.println("Invalid Position");
                        break;
                    }
                    System.out.println("Enter the Item");
                    linkedList.insertAtPosition(position, scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 4:
                try {
                    System.out.println("Enter the position");
                    int position = scanner.nextInt();
                    if (position < 1 || position > linkedList.size()) {
                        System.out.println("Invalid Position");
                        break;
                    }
                    linkedList.delete(position);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 5:
                try {
                    linkedList.display();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 6:
                System.out.println(linkedList.empty());
                break;

            case 7:
                try {
                    System.out.println(linkedList.size());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 8:
                try {
                    System.out.println(linkedList.index(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 9:
                try {
                    System.out.println("Enter the position");
                    int position = scanner.nextInt();
                    if (position < 1 || position > linkedList.size()) {
                        System.out.println("Invalid Position");
                        break;
                    }
                    linkedList.replace(position, scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 10:
                try {
                    System.out.println("Enter the position");
                    int position = scanner.nextInt();
                    if (position < 1 || position > linkedList.size()) {
                        System.out.println("Invalid Position");
                        break;
                    }
                    System.out.println("Enter the item");
                    linkedList.replaceRecursively(position, scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 11:
                try {
                    System.out.println(linkedList.middle());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 12:
                try {
                    System.out.println("Enter the item");
                    System.out.println(linkedList.occurence(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 13:
                try {
                    linkedList.reverseRecusively();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 14:
                try {
                    linkedList.reverse();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 15:
                try {
                    System.out.println("Enter the nodes");
                    linkedList.swapNode(scanner.nextInt(), scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 16:
                try {
                    System.out.println("Enter which node do you want from last");
                    linkedList.printNthNodeFromLast(scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            default:
                System.out.println("Invalid Choice");
                break;
            }
        } while (yes);
        scanner.close();
    }
}

Answer 4

Здесь мы видим простую реализацию LinkedList с итератором

    class LinkedList implements Iterable{
        private Node node;
        public void add(Object data){
            if(!Optional.ofNullable(node).isPresent()){
                node = new Node();
                node.setData(data);
            }else{
                Node node = new Node();
                node.setData(data);
                Node lastNode = getLastNode(this.node);
                lastNode.setNext(node);
            }
        }

        private Node getLastNode(Node node){
            if(node.getNext()==null){
                return node;
            }else{
                return getLastNode(node.getNext());
            }
        } 

        class Node{
            private Object data;
            private Node next;
            public Object getData() {
                return data;
            }
            public void setData(Object data) {
                this.data = data;
            }
            public Node getNext() {
                return next;
            }
            public void setNext(Node next) {
                this.next = next;
            }
        }

        public Iterator iterator() {
            return new NodeIterator();
        }

        class NodeIterator implements Iterator{
            private Node current;

            public boolean hasNext() {
                if(current == null){
                    current = node;
                    return Optional.ofNullable(current).isPresent();
                }else{
                    current = current.next;
                    return Optional.ofNullable(current).isPresent();
                }
            }

            public Node next() {
                return current;
            }
        }
    }

    public class LinkedListImpl {
        public static void main(String[] args) {
            LinkedList linkedList = new LinkedList();
            linkedList.add("data1");
            linkedList.add("data2");
            linkedList.add("data3");
            for(LinkedList.Node node: linkedList){
                System.out.println(node.getData());
            }
        }
    }