Создание classа LinkedList с нуля

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

public class LinkedList { private LinkedList next; private final String word; // constructor public LinkedList(String word, LinkedList next) { this.word = word; this.next = next; } 

И, таким образом, у нас есть связанный список. Что происходит? Как создать связанный список? Как это работает? Я должен написать метод append, который добавляет данный параметр String word в конец this связанного списка. Я попытался взглянуть на встроенный метод addLast для встроенного classа java связанного списка, но мне это не помогает, поскольку я действительно не понимаю, что происходит. Кто-нибудь хочет помочь мне 🙂

    Если вы на самом деле создаете реальную систему, то да, вы обычно просто используете материал в стандартной библиотеке, если то, что вам нужно, доступно там. Тем не менее, не думайте об этом как о бессмысленной практике. Хорошо понимать, как все работает, и понимать связанные списки – важный шаг к пониманию более сложных структур данных, многие из которых не существуют в стандартных библиотеках.

    Существуют некоторые различия между тем, как вы создаете связанный список, и тем, как это делает API коллекций Java. API коллекций пытается придерживаться более сложного интерфейса. Связанный с коллекцией API список также является дважды связанным списком, в то время как вы создаете отдельный список. То, что вы делаете, более подходит для присвоения classа.

    С вашим classом LinkedList экземпляр всегда будет списком хотя бы одного элемента. При такой настройке вы должны использовать null если вам нужен пустой список.

    Подумайте о next как о «остальной части списка». На самом деле, многие подобные реализации используют имя «хвост» вместо «next».

    Вот диаграмма LinkedList содержащая 3 элемента:

    диаграмма связанного списка

    Обратите внимание, что это объект LinkedList указывающий на слово («Hello») и список из двух элементов. Список из 2 элементов имеет слово («Stack») и список из 1 элемента. В этом списке из 1 элемента есть слово («Переполнение») и пустой список ( null ). Таким образом, вы можете рассматривать next как просто другой список, который, как оказалось, является одним из элементов короче.

    Вы можете добавить другой конструктор, который просто берет строку, и устанавливает рядом с null . Это было бы для создания 1-элементного списка.

    Чтобы добавить, вы проверяете, имеет ли next null . Если это так, создайте новый список элементов и установите next с ним.

     next = new LinkedList(word); 

    Если next не равен null , то вместо этого добавьте к next .

     next.append(word); 

    Это рекурсивный подход, который является наименьшим количеством кода. Вы можете превратить это в итеративное решение, которое было бы более эффективным в Java * и не подвергло бы риску переполнение стека с очень длинными списками, но я предполагаю, что уровень сложности не требуется для вашего назначения.


    * Некоторые языки устраняют устранение хвоста, что является оптимизацией, которая позволяет языковой реализации преобразовывать «хвосты» (вызов другой функции как последний шаг перед возвратом) в (эффективно) «goto». Это приводит к тому, что такой код полностью избегает использования стека, что делает его более безопасным (вы не можете переполнять стек, если вы не используете стек) и обычно более эффективны. Схема, вероятно, является наиболее известным примером языка с этой функцией.

    То, что вы закодировали, не LinkedList , по крайней мере, не тот, который я узнаю. Для этого задания вы хотите создать два classа:

     LinkNode LinkedList 

    LinkNode имеет одно поле-член для содержащихся в нем данных и ссылку LinkNode для следующего LinkNode в LinkedList . Да, это самореферентная структура данных. Ссылка LinkedList имеет специальную ссылку LinkNode которая ссылается на первый элемент в списке.

    Когда вы добавляете элемент в LinkedList , вы перемещаете все LinkNode's пока не достигнете последнего. Следующий LinkNode's должен быть нулевым. Затем вы LinkNode новый LinkNode , устанавливаете его значение и добавляете его в LinkedList .

     public class LinkNode { String data; LinkNode next; public LinkNode(String item) { data = item; } } public class LinkedList { LinkNode head; public LinkedList(String item) { head = new LinkNode(item); } public void add(String item) { //pseudo code: while next isn't null, walk the list //once you reach the end, create a new LinkNode and add the item to it. Then //set the last LinkNode's next to this new LinkNode } } 

    Как насчет полностью функциональной реализации нерекурсивного Linked List?

    Я создал это для своих алгоритмов I classа как ступеньку, чтобы получить лучшее понимание, прежде чем переходить к написанию дважды связанного classа очереди для назначения.

    Вот код:

     import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedList implements Iterable { 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("The first argument for addLast() is null."); } 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("Cannot remove() from and 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 iterator() { return new LinkedListIterator(); } private class LinkedListIterator implements Iterator { 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 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; } } } , import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedList implements Iterable { 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("The first argument for addLast() is null."); } 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("Cannot remove() from and 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 iterator() { return new LinkedListIterator(); } private class LinkedListIterator implements Iterator { 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 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; } } } 

    Примечание. Это довольно простая реализация одноуровневого списка. Тип «T» является заполнитель типа общего типа. В принципе, этот связанный список должен работать с любым типом, который наследуется от Object. Если вы используете его для примитивных типов, обязательно используйте эквивалентные эквивалентные classы (ex ‘Integer’ для типа ‘int’). «Последняя» переменная действительно не нужна, за исключением того, что она сокращает вставки в O (1) раз. Удаление происходит медленно, так как они работают в O (N) раз, но это позволяет удалить первое вхождение значения в списке.

    Если вы хотите, вы также можете изучить:

    • addFirst () – добавить новый элемент в начало LinkedList
    • removeFirst () – удалить первый элемент из LinkedList
    • removeLast () – удалить последний элемент из LinkedList
    • addAll () – добавить список / массив элементов в LinkedList
    • removeAll () – удалить список / массив элементов из LinkedList
    • contains () – проверить, содержит ли LinkedList элемент
    • contains () – очистить все элементы в LinkedList

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

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

    Есть три команды для проверки этого в отладчике / консоли:

    • Префикс значения «+» добавит его в список.
    • Префикс с «-» удалит первое вхождение из списка.
    • Ввод «print» распечатает список со значениями, разделенными пробелами.

    Если вы никогда не видели внутренности, как одна из этих работ, я предлагаю вам выполнить следующие действия в отладчике:

    • add () – накладывает новый узел на конец или инициализирует первые / последние значения, если список пуст
    • remove () – просматривает список из начала до конца. Если он находит совпадение, он удаляет этот элемент и связывает неработающие ссылки между предыдущими и следующими ссылками в цепочке. Особые исключения добавляются, когда нет предыдущей или следующей ссылки.
    • toString () – использует iterator foreach, чтобы просто перемещаться по цепочке списка от начала до конца.

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

    Подсказка 1: прочитайте описание связанных списков по адресу http://en.wikipedia.org/wiki/Linked_list

    Подсказка 2: реализация Java LinkedList является двусвязным списком. Твой – это отдельный список. Алгоритмы не применяются напрямую.


    Также:

    … но создание [связанного classа списка] с нуля не имеет никакого смысла.

    Это зависит от того, каков требуемый результат работы. Если целью является создание кода, отвечающего определенным функциональным / нефункциональным требованиям, то вы правы. Если реальная цель заключается в том, чтобы вы научились программировать / проектировать API / внедрять нетривиальные структуры данных, то полезность конечного продукта почти не имеет значения.

    И, таким образом, у нас есть связанный список

    У вас на самом деле есть открытый тип данных, который можно использовать для создания (сортировки) списка. Но это не то, чего хочет ваш учитель. И это, безусловно, не будет считаться полезной абстракцией списка. Полезная абстракция будет включать:

    • методы делать то, что программисты не хотят повторять снова и снова, и

    • слой абстракции, который останавливает программистов, «ломающих» список; например, путем случайного создания цикла или случайного сшивания подсписок в двух списках для создания перевернутого дерева.

    Конечно, связанный список немного запутан для программирования n00bs, в значительной степени соблазн – посмотреть на него как на Russian Dolls, потому что это похоже на объект LinkedList в объекте LinkedList. Но это трудно понять, а не смотреть на него как на компьютер.

    LinkedList = Data + Next Member

    Где это последний член списка, если следующий – NULL

    Таким образом, 5-элементный LinkedList будет:

    LinkedList (Data1, LinkedList (Data2, LinkedList (Data3, LinkedList (Data4, LinkedList (Data5, NULL)))))

    Но вы можете думать об этом просто:

    Data1 -> Data2 -> Data3 -> Data4 -> Data5 -> NULL

    Итак, как мы находим конец этого? Ну, мы знаем, что NULL – это конец:

     public void append(LinkedList myNextNode) { LinkedList current = this; //Make a variable to store a pointer to this LinkedList while (current.next != NULL) { //While we're not at the last node of the LinkedList current = current.next; //Go further down the rabbit hole. } current.next = myNextNode; //Now we're at the end, so simply replace the NULL with another Linked List! return; //and we're done! } 

    Конечно, это очень простой код, и он будет бесконечно зацикливаться, если вы будете кормить его круговым списком! Но это основа.

    Программа со связанными списками со следующими функциональными возможностями

     1 Insert At Start 2 Insert At End 3 Insert At any Position 4 Delete At any Position 5 Display 6 Get Size 7 Empty Status 8 Replace data at given postion 9 Search Element by position 10 Delete a Node by Given Data 11 Search Element Iteratively 12 Search Element Recursively package com.elegant.ds.linkedlist.practice; import java.util.Scanner; class Node { Node link = null; int data = 0; public Node() { link = null; data = 0; } public Node(int data, Node link) { this.data = data; this.link = null; } public Node getLink() { return link; } public void setLink(Node link) { this.link = link; } public int getData() { return data; } public void setData(int data) { this.data = data; } } class SinglyLinkedListImpl { Node start = null; Node end = null; int size = 0; public SinglyLinkedListImpl() { start = null; end = null; size = 0; } public void insertAtStart(int data) { Node nptr = new Node(data, null); if (start == null) { start = nptr; end = start; } else { nptr.setLink(start); start = nptr; } size++; } public void insertAtEnd(int data) { Node nptr = new Node(data, null); if (start == null) { start = nptr; end = nptr; } else { end.setLink(nptr); end = nptr; } size++; } public void insertAtPosition(int position, int data) { Node nptr = new Node(data, null); Node ptr = start; position = position - 1; for (int i = 1; i < size; i++) { if (i == position) { Node temp = ptr.getLink(); ptr.setLink(nptr); nptr.setLink(temp); break; } ptr = ptr.getLink(); } size++; } public void repleaceDataAtPosition(int position, int data) { if (start == null) { System.out.println("Empty!"); return; } Node ptr = start; for (int i = 1; i < size; i++) { if (i == position) { ptr.setData(data); } ptr = ptr.getLink(); } } public void deleteAtPosition(int position) { if (start == null) { System.out.println("Empty!"); return; } if (position == size) { Node startPtr = start; Node endPtr = start; while (startPtr != null) { endPtr = startPtr; startPtr = startPtr.getLink(); } end = endPtr; end.setLink(null); size--; return; } Node ptr = start; position = position - 1; for (int i = 1; i < size; i++) { if (i == position) { Node temp = ptr.getLink(); temp = temp.getLink(); ptr.setLink(temp); break; } ptr = ptr.getLink(); } size--; } public void deleteNodeByGivenData(int data) { if (start == null) { System.out.println("Empty!"); return; } if (start.getData() == data && start.getLink() == null) { start = null; end = null; size--; return; } if (start.getData() == data && start.getLink() != null) { start = start.getLink(); size--; return; } if (end.getData() == data) { Node startPtr = start; Node endPtr = start; startPtr = startPtr.getLink(); while (startPtr.getLink() != null) { endPtr = startPtr; startPtr = startPtr.getLink(); } end = endPtr; end.setLink(null); size--; return; } Node startPtr = start; Node prevLink = startPtr; startPtr = startPtr.getLink(); while (startPtr.getData() != data && startPtr.getLink() != null) { prevLink = startPtr; startPtr = startPtr.getLink(); } if (startPtr.getData() == data) { Node temp = prevLink.getLink(); temp = temp.getLink(); prevLink.setLink(temp); size--; return; } System.out.println(data + " not found!"); } public void disply() { if (start == null) { System.out.println("Empty!"); return; } if (start.getLink() == null) { System.out.println(start.getData()); return; } Node ptr = start; System.out.print(ptr.getData() + "->"); ptr = start.getLink(); while (ptr.getLink() != null) { System.out.print(ptr.getData() + "->"); ptr = ptr.getLink(); } System.out.println(ptr.getData() + "\n"); } public void searchElementByPosition(int position) { if (position == 1) { System.out.println("Element at " + position + " is : " + start.getData()); return; } if (position == size) { System.out.println("Element at " + position + " is : " + end.getData()); return; } Node ptr = start; for (int i = 1; i < size; i++) { if (i == position) { System.out.println("Element at " + position + " is : " + ptr.getData()); break; } ptr = ptr.getLink(); } } public void searchElementIteratively(int data) { if (isEmpty()) { System.out.println("Empty!"); return; } if (start.getData() == data) { System.out.println(data + " found at " + 1 + " position"); return; } if (start.getLink() != null && end.getData() == data) { System.out.println(data + " found at " + size + " position"); return; } Node startPtr = start; int position = 0; while (startPtr.getLink() != null) { ++position; if (startPtr.getData() == data) { break; } startPtr = startPtr.getLink(); } if (startPtr.getData() == data) { System.out.println(data + " found at " + position); return; } System.out.println(data + " No found!"); } public void searchElementRecursively(Node start, int data, int count) { if (isEmpty()) { System.out.println("Empty!"); return; } if (start.getData() == data) { System.out.println(data + " found at " + (++count)); return; } if (start.getLink() == null) { System.out.println(data + " not found!"); return; } searchElementRecursively(start.getLink(), data, ++count); } public int getSize() { return size; } public boolean isEmpty() { return start == null; } } public class SinglyLinkedList { @SuppressWarnings("resource") public static void main(String[] args) { SinglyLinkedListImpl listImpl = new SinglyLinkedListImpl(); System.out.println("Singly Linked list : "); boolean yes = true; do { System.out.println("1 Insert At Start :"); System.out.println("2 Insert At End :"); System.out.println("3 Insert At any Position :"); System.out.println("4 Delete At any Position :"); System.out.println("5 Display :"); System.out.println("6 Get Size"); System.out.println("7 Empty Status"); System.out.println("8 Replace data at given postion"); System.out.println("9 Search Element by position "); System.out.println("10 Delete a Node by Given Data"); System.out.println("11 Search Element Iteratively"); System.out.println("12 Search Element Recursively"); System.out.println("13 Exit :"); Scanner scanner = new Scanner(System.in); int choice = scanner.nextInt(); switch (choice) { case 1: listImpl.insertAtStart(scanner.nextInt()); break; case 2: listImpl.insertAtEnd(scanner.nextInt()); break; case 3: int position = scanner.nextInt(); if (position <= 1 || position > listImpl.getSize()) { System.out.println("invalid position!"); } else { listImpl.insertAtPosition(position, scanner.nextInt()); } break; case 4: int deletePosition = scanner.nextInt(); if (deletePosition <= 1 || deletePosition > listImpl.getSize()) { System.out.println("invalid position!"); } else { listImpl.deleteAtPosition(deletePosition); } break; case 5: listImpl.disply(); break; case 6: System.out.println(listImpl.getSize()); break; case 7: System.out.println(listImpl.isEmpty()); break; case 8: int replacePosition = scanner.nextInt(); if (replacePosition < 1 || replacePosition > listImpl.getSize()) { System.out.println("Invalid position!"); } else { listImpl.repleaceDataAtPosition(replacePosition, scanner.nextInt()); } break; case 9: int searchPosition = scanner.nextInt(); if (searchPosition < 1 || searchPosition > listImpl.getSize()) { System.out.println("Invalid position!"); } else { listImpl.searchElementByPosition(searchPosition); } break; case 10: listImpl.deleteNodeByGivenData(scanner.nextInt()); break; case 11: listImpl.searchElementIteratively(scanner.nextInt()); break; case 12: listImpl.searchElementRecursively(listImpl.start, scanner.nextInt(), 0); break; default: System.out.println("invalid choice"); break; } } while (yes); } } 

    Это поможет вам в связанном списке.

    Связанный список для демонстрации «Вставить передний», «Удалить фронт», «Вставить задний» и «Удалить» Задние операции в Java:

     import java.io.DataInputStream; import java.io.IOException; public class LinkedListTest { public static void main(String[] args) { // TODO Auto-generated method stub Node root = null; DataInputStream reader = new DataInputStream(System.in); int op = 0; while(op != 6){ try { System.out.println("Enter Option:\n1:Insert Front 2:Delete Front 3:Insert Rear 4:Delete Rear 5:Display List 6:Exit"); //op = reader.nextInt(); op = Integer.parseInt(reader.readLine()); switch (op) { case 1: System.out.println("Enter Value: "); int val = Integer.parseInt(reader.readLine()); root = insertNodeFront(val,root); display(root); break; case 2: root=removeNodeFront(root); display(root); break; case 3: System.out.println("Enter Value: "); val = Integer.parseInt(reader.readLine()); root = insertNodeRear(val,root); display(root); break; case 4: root=removeNodeRear(root); display(root); break; case 5: display(root); break; default: System.out.println("Invalid Option"); break; } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } System.out.println("Exited!!!"); try { reader.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } static Node insertNodeFront(int value, Node root){ Node temp = new Node(value); if(root==null){ return temp; // as root or first } else { temp.next = root; return temp; } } static Node removeNodeFront(Node root){ if(root==null){ System.out.println("List is Empty"); return null; } if(root.next==null){ return null; // remove root itself } else { root=root.next;// make next node as root return root; } } static Node insertNodeRear(int value, Node root){ Node temp = new Node(value); Node cur = root; if(root==null){ return temp; // as root or first } else { while(cur.next!=null) { cur = cur.next; } cur.next = temp; return root; } } static Node removeNodeRear(Node root){ if(root==null){ System.out.println("List is Empty"); return null; } Node cur = root; Node prev = null; if(root.next==null){ return null; // remove root itself } else { while(cur.next!=null) { prev = cur; cur = cur.next; } prev.next=null;// remove last node return root; } } static void display(Node root){ System.out.println("Current List:"); if(root==null){ System.out.println("List is Empty"); return; } while (root!=null){ System.out.print(root.val+"->"); root=root.next; } System.out.println(); } static class Node{ int val; Node next; public Node(int value) { // TODO Auto-generated constructor stub val = value; next = null; } } } в import java.io.DataInputStream; import java.io.IOException; public class LinkedListTest { public static void main(String[] args) { // TODO Auto-generated method stub Node root = null; DataInputStream reader = new DataInputStream(System.in); int op = 0; while(op != 6){ try { System.out.println("Enter Option:\n1:Insert Front 2:Delete Front 3:Insert Rear 4:Delete Rear 5:Display List 6:Exit"); //op = reader.nextInt(); op = Integer.parseInt(reader.readLine()); switch (op) { case 1: System.out.println("Enter Value: "); int val = Integer.parseInt(reader.readLine()); root = insertNodeFront(val,root); display(root); break; case 2: root=removeNodeFront(root); display(root); break; case 3: System.out.println("Enter Value: "); val = Integer.parseInt(reader.readLine()); root = insertNodeRear(val,root); display(root); break; case 4: root=removeNodeRear(root); display(root); break; case 5: display(root); break; default: System.out.println("Invalid Option"); break; } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } System.out.println("Exited!!!"); try { reader.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } static Node insertNodeFront(int value, Node root){ Node temp = new Node(value); if(root==null){ return temp; // as root or first } else { temp.next = root; return temp; } } static Node removeNodeFront(Node root){ if(root==null){ System.out.println("List is Empty"); return null; } if(root.next==null){ return null; // remove root itself } else { root=root.next;// make next node as root return root; } } static Node insertNodeRear(int value, Node root){ Node temp = new Node(value); Node cur = root; if(root==null){ return temp; // as root or first } else { while(cur.next!=null) { cur = cur.next; } cur.next = temp; return root; } } static Node removeNodeRear(Node root){ if(root==null){ System.out.println("List is Empty"); return null; } Node cur = root; Node prev = null; if(root.next==null){ return null; // remove root itself } else { while(cur.next!=null) { prev = cur; cur = cur.next; } prev.next=null;// remove last node return root; } } static void display(Node root){ System.out.println("Current List:"); if(root==null){ System.out.println("List is Empty"); return; } while (root!=null){ System.out.print(root.val+"->"); root=root.next; } System.out.println(); } static class Node{ int val; Node next; public Node(int value) { // TODO Auto-generated constructor stub val = value; next = null; } } } в import java.io.DataInputStream; import java.io.IOException; public class LinkedListTest { public static void main(String[] args) { // TODO Auto-generated method stub Node root = null; DataInputStream reader = new DataInputStream(System.in); int op = 0; while(op != 6){ try { System.out.println("Enter Option:\n1:Insert Front 2:Delete Front 3:Insert Rear 4:Delete Rear 5:Display List 6:Exit"); //op = reader.nextInt(); op = Integer.parseInt(reader.readLine()); switch (op) { case 1: System.out.println("Enter Value: "); int val = Integer.parseInt(reader.readLine()); root = insertNodeFront(val,root); display(root); break; case 2: root=removeNodeFront(root); display(root); break; case 3: System.out.println("Enter Value: "); val = Integer.parseInt(reader.readLine()); root = insertNodeRear(val,root); display(root); break; case 4: root=removeNodeRear(root); display(root); break; case 5: display(root); break; default: System.out.println("Invalid Option"); break; } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } System.out.println("Exited!!!"); try { reader.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } static Node insertNodeFront(int value, Node root){ Node temp = new Node(value); if(root==null){ return temp; // as root or first } else { temp.next = root; return temp; } } static Node removeNodeFront(Node root){ if(root==null){ System.out.println("List is Empty"); return null; } if(root.next==null){ return null; // remove root itself } else { root=root.next;// make next node as root return root; } } static Node insertNodeRear(int value, Node root){ Node temp = new Node(value); Node cur = root; if(root==null){ return temp; // as root or first } else { while(cur.next!=null) { cur = cur.next; } cur.next = temp; return root; } } static Node removeNodeRear(Node root){ if(root==null){ System.out.println("List is Empty"); return null; } Node cur = root; Node prev = null; if(root.next==null){ return null; // remove root itself } else { while(cur.next!=null) { prev = cur; cur = cur.next; } prev.next=null;// remove last node return root; } } static void display(Node root){ System.out.println("Current List:"); if(root==null){ System.out.println("List is Empty"); return; } while (root!=null){ System.out.print(root.val+"->"); root=root.next; } System.out.println(); } static class Node{ int val; Node next; public Node(int value) { // TODO Auto-generated constructor stub val = value; next = null; } } } 

    Как я создал связанный список, как это. Как это работает? Это все связанный список. Элемент со ссылкой на следующий элемент в списке. Пока вы сохраняете ссылку на элемент в начале списка, вы можете пройти все это, используя каждую последующую ссылку на следующее значение.

    Чтобы добавить, все, что вам нужно сделать, это найти конец списка и сделать следующий элемент значением, которое вы хотите добавить, поэтому, если это не имеет значения null, вам нужно будет вызвать append на следующем элементе, пока не найдете конец списка.

     this.next.Append(word); 

    Только что сделал gistub по внедрению LinkedList из Scratch. Может помочь. Проверьте это.

    https://gist.github.com/akshaynagpal/14ee8b54cd018bd05b2a3c2432c818dc

    Пожалуйста, прочитайте эту статью: Как реализовать class LinkedList с нуля в Java

     package com.crunchify.tutorials; /** * @author Crunchify.com */ public class CrunchifyLinkedListTest { public static void main(String[] args) { CrunchifyLinkedList lList = new CrunchifyLinkedList(); // add elements to LinkedList lList.add("1"); lList.add("2"); lList.add("3"); lList.add("4"); lList.add("5"); /* * Please note that primitive values can not be added into LinkedList * directly. They must be converted to their corresponding wrapper * class. */ System.out.println("lList - print linkedlist: " + lList); System.out.println("lList.size() - print linkedlist size: " + lList.size()); System.out.println("lList.get(3) - get 3rd element: " + lList.get(3)); System.out.println("lList.remove(2) - remove 2nd element: " + lList.remove(2)); System.out.println("lList.get(3) - get 3rd element: " + lList.get(3)); System.out.println("lList.size() - print linkedlist size: " + lList.size()); System.out.println("lList - print linkedlist: " + lList); } } class CrunchifyLinkedList { // reference to the head node. private Node head; private int listCount; // LinkedList constructor public CrunchifyLinkedList() { // this is an empty list, so the reference to the head node // is set to a new node with no data head = new Node(null); listCount = 0; } public void add(Object data) // appends the specified element to the end of this list. { Node crunchifyTemp = new Node(data); Node crunchifyCurrent = head; // starting at the head node, crawl to the end of the list while (crunchifyCurrent.getNext() != null) { crunchifyCurrent = crunchifyCurrent.getNext(); } // the last node's "next" reference set to our new node crunchifyCurrent.setNext(crunchifyTemp); listCount++;// increment the number of elements variable } public void add(Object data, int index) // inserts the specified element at the specified position in this list { Node crunchifyTemp = new Node(data); Node crunchifyCurrent = head; // crawl to the requested index or the last element in the list, // whichever comes first for (int i = 1; i < index && crunchifyCurrent.getNext() != null; i++) { crunchifyCurrent = crunchifyCurrent.getNext(); } // set the new node's next-node reference to this node's next-node // reference crunchifyTemp.setNext(crunchifyCurrent.getNext()); // now set this node's next-node reference to the new node crunchifyCurrent.setNext(crunchifyTemp); listCount++;// increment the number of elements variable } public Object get(int index) // returns the element at the specified position in this list. { // index must be 1 or higher if (index <= 0) return null; Node crunchifyCurrent = head.getNext(); for (int i = 1; i < index; i++) { if (crunchifyCurrent.getNext() == null) return null; crunchifyCurrent = crunchifyCurrent.getNext(); } return crunchifyCurrent.getData(); } public boolean remove(int index) // removes the element at the specified position in this list. { // if the index is out of range, exit if (index < 1 || index > size()) return false; Node crunchifyCurrent = head; for (int i = 1; i < index; i++) { if (crunchifyCurrent.getNext() == null) return false; crunchifyCurrent = crunchifyCurrent.getNext(); } crunchifyCurrent.setNext(crunchifyCurrent.getNext().getNext()); listCount--; // decrement the number of elements variable return true; } public int size() // returns the number of elements in this list. { return listCount; } public String toString() { Node crunchifyCurrent = head.getNext(); String output = ""; while (crunchifyCurrent != null) { output += "[" + crunchifyCurrent.getData().toString() + "]"; crunchifyCurrent = crunchifyCurrent.getNext(); } return output; } private class Node { // reference to the next node in the chain, // or null if there isn't one. Node next; // data carried by this node. // could be of any type you need. Object data; // Node constructor public Node(Object dataValue) { next = null; data = dataValue; } // another Node constructor if we want to // specify the node to point to. public Node(Object dataValue, Node nextValue) { next = nextValue; data = dataValue; } // these methods should be self-explanatory public Object getData() { return data; } public void setData(Object dataValue) { data = dataValue; } public Node getNext() { return next; } public void setNext(Node nextValue) { next = nextValue; } } } 

    Вывод

     lList - print linkedlist: [1][2][3][4][5] lList.size() - print linkedlist size: 5 lList.get(3) - get 3rd element: 3 lList.remove(2) - remove 2nd element: true lList.get(3) - get 3rd element: 4 lList.size() - print linkedlist size: 4 lList - print linkedlist: [1][3][4][5] 

    Просьба найти следующую программу

     class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } public class LinkedListManual { Node node; public void pushElement(int next_node) { Node nd = new Node(next_node); nd.next = node; node = nd; } public int getSize() { Node temp = node; int count = 0; while (temp != null) { count++; temp = temp.next; } return count; } public void getElement() { Node temp = node; while (temp != null) { System.out.println(temp.data); temp = temp.next; } } public static void main(String[] args) { LinkedListManual obj = new LinkedListManual(); obj.pushElement(1); obj.pushElement(2); obj.pushElement(3); obj.getElement(); //get element System.out.println(obj.getSize()); //get size of link list } } 
     class Node { int data; Node link; public Node() { data=0; link=null; } Node ptr,start,temp; void create()throws IOException { int n; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter first data"); this.data=Integer.parseInt(br.readLine()); ptr=this; start=ptr; char ins ='y'; do { System.out.println("Wanna Insert another node???"); ins=(char)br.read(); br.read(); if(ins=='y') { temp=new Node(); System.out.println("Enter next data"); temp.data=Integer.parseInt(br.readLine()); temp.link=null; ptr.link=temp; temp=null; ptr=ptr.link; } }while(ins=='y'); } public static void main(String args[])throws IOException { Node first= new Node(); first.create(); } } в class Node { int data; Node link; public Node() { data=0; link=null; } Node ptr,start,temp; void create()throws IOException { int n; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter first data"); this.data=Integer.parseInt(br.readLine()); ptr=this; start=ptr; char ins ='y'; do { System.out.println("Wanna Insert another node???"); ins=(char)br.read(); br.read(); if(ins=='y') { temp=new Node(); System.out.println("Enter next data"); temp.data=Integer.parseInt(br.readLine()); temp.link=null; ptr.link=temp; temp=null; ptr=ptr.link; } }while(ins=='y'); } public static void main(String args[])throws IOException { Node first= new Node(); first.create(); } } 
    Давайте будем гением компьютера.