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

Question

Добавить в односвязный список новый элемент L за каждым вхождением элемента Е. Например, допустим есть список элементов 2, 3, 4, 7, 23, 2, 4. С консоли мы вводим еще два элемента. Например L=55 и E=4.После этого программа должна выдать новый список 2,3,4,55,7,23,2,4,55. Я смог реализовать только список. Я пытался создать в методе insert и в отдельном методе, но никак не могу додуматься. Как мне реализовать?

import java.io.*;
import java.util.Scanner;
import java.util.NoSuchElementException;

public class LinkedList {
    Node head; // head of list

    static class Node {

        int data;
        Node next;

        // Constructor

        Node(int d) {
            data = d;
            next = null;
        }

        // Method to insert a new node
        public static LinkedList insert(LinkedList list, int data) {
            // Create a new node with given data
            Node new_node = new Node(data);
            new_node.next = null;

            // If the Linked List is empty,
            // then make the new node as head
            if (list.head == null) {
                list.head = new_node;
            } else {
                // Else traverse till the last node
                // and insert the new_node there
                Node last = list.head;
                while (last.next != null) {
                    last = last.next;
                }

                // Insert the new_node at last node
                last.next = new_node;
            }

            // Return the list by head
            return list;
        }

        // Method to print the LinkedList.
        public static void printList(LinkedList list) {
            Node currNode = list.head;

            System.out.print("LinkedList: ");

            // Traverse through the LinkedList
            while (currNode != null) {
                // Print the data at current node
                System.out.print(currNode.data + " ");

                // Go to next node
                currNode = currNode.next;
            }

            System.out.println();
        }

public static void main(String[] args) {

            LinkedList list = new LinkedList();

            //
            // ******INSERTION******
            //

            // Insert the values
            list = insert(list, 1);
            list = insert(list, 2);
            list = insert(list, 3);
            list = insert(list, 4);
            list = insert(list, 5);
            list = insert(list, 6);
            list = insert(list, 7);
            list = insert(list, 8);

            // Print the LinkedList
            printList(list);
        }
    }
}

Answer 1

Ваш код, как я уже написал содержит слабости. Вершины Node должны агрегироваться, а реализовываться отдельным классом (никак не внутренним). Давайте договоримся, вы перед тем как реализовывать велосипед, сначала загуглите как он пишется. В интернете мужики уже реализовали гораздо лучше вас и даже меня. За исходник я взял этот код и он мне понравился.

class ListElement {
    ListElement next;    // указатель на следующий элемент
    int data;            // данные
}

class List {
    private ListElement head;       // указатель на первый элемент
    private ListElement tail;       // указатель последний элемент

    void addFront(int data)           //добавить спереди
    {
        ListElement a = new ListElement();  //создаём новый элемент
        a.data = data;              //инициализируем данные.
        // указатель на следующий элемент автоматически инициализируется как null
        if(head == null)            //если список пуст
        {                           //то указываем ссылки начала и конца на новый элемент
            head = a;               //т.е. список теперь состоит из одного элемента
            tail = a;
        }
        else {
            a.next = head;          //иначе новый элемент теперь ссылается на "бывший" первый
            head = a;               //а указатель на первый элемент теперь ссылается на новый элемент
        }
    }

    void addBack(int data) {          //добавление в конец списка
        ListElement a = new ListElement();  //создаём новый элемент
        a.data = data;
        if (tail == null)           //если список пуст
        {                           //то указываем ссылки начала и конца на новый элемент
            head = a;               //т.е. список теперь состоит из одного элемента
            tail = a;
        } else {
            tail.next = a;          //иначе "старый" последний элемент теперь ссылается на новый
            tail = a;               //а в указатель на последний элемент записываем адрес нового элемента
        }
    }

    void printList()                //печать списка
    {
        ListElement t = this.head;       //получаем ссылку на первый элемент
        while (t != null)           //пока элемент существуе
        {
            System.out.print(t.data + " "); //печатаем его данные
            t = t.next;                     //и переключаемся на следующий
        }
        System.out.println();
    }


    public void addAfter(int prevEl, int nextEl){//Мстод который задали вам
        ListElement t = this.head; //Получаем ссылку на первоэлемент
        while (t!=null){
            if(prevEl==t.data){
                ListElement e = new ListElement();
                e.data = nextEl;
                e.next = t.next;
                t.next = e;
                t =e;
            }
           t = t.next;
        }

    } 

    void delEl(int data)          //удаление элемента
    {
        if(head == null)        //если список пуст -
            return;             //ничего не делаем

        if (head == tail) {     //если список состоит из одного элемента
            head = null;        //очищаем указатели начала и конца
            tail = null;
            return;             //и выходим
        }

        if (head.data == data) {    //если первый элемент - тот, что нам нужен
            head = head.next;       //переключаем указатель начала на второй элемент
            return;                 //и выходим
        }

        ListElement t = head;       //иначе начинаем искать
        while (t.next != null) {    //пока следующий элемент существует
            if (t.next.data == data) {  //проверяем следующий элемент
                if(tail == t.next)      //если он последний
                {
                    tail = t;           //то переключаем указатель на последний элемент на текущий
                }
                t.next = t.next.next;   //найденный элемент выкидываем
                return;                 //и выходим
            }
            t = t.next;                //иначе ищем дальше
        }
    }
}

public class ListTest {
    public static void main(String[] args) {
        List l = new List();
        for(int i = 0; i<=5; i++){
            l.addBack(i);
        }
        l.printList();
        l.addAfter(4, 4);
        l.printList();
    }
}

Метод public void addAfter(int prevEl, int nextEl) - я реализовал за вас, что непонятно - спрашивайте в комментариях. Класс ListTest - для того чтобы протестировать ваш список. Я протестировал - вроде работает.

БЛОГ НА HUSL

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

Ответы (1 шт):