Как создать структуру данных связанного списка в Java? [закрыто]

Какой лучший способ сделать связанный список в Java?

13.08.2008 16:29:22
Лучший способ создать связанный список - использовать встроенный связанный список. Не переписывайте встроенные классы.
Peter Lawrey 26.12.2009 17:26:00
этот вопрос является законным и очень конструктивным для обсуждения программистами
anshulkatta 25.05.2014 09:36:41
6 ОТВЕТОВ
РЕШЕНИЕ

Очевидным решением для разработчиков, знакомых с Java, является использование класса LinkedList, уже предоставленного в java.util . Скажем, однако, вы хотели сделать собственную реализацию по какой-то причине. Вот краткий пример связанного списка, который вставляет новую ссылку в начало списка, удаляет из начала списка и циклически перебирает список, чтобы напечатать содержащиеся в нем ссылки. Усовершенствования этой реализации включают создание двойного связанного списка , добавление методов для вставки и удаления из середины или конца, а также добавление методов get и sort .

Примечание . В этом примере объект Link на самом деле не содержит другого объекта Link - nextLink на самом деле является только ссылкой на другую ссылку.

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    //Link constructor
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    //Print Link data
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

class LinkList {
    private Link first;

    //LinkList constructor
    public LinkList() {
        first = null;
    }

    //Returns true if list is empty
    public boolean isEmpty() {
        return first == null;
    }

    //Inserts a new Link at the first of the list
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    //Deletes the link at the first of the list
    public Link delete() {
        Link temp = first;
        if(first == null){
         return null;
         //throw new NoSuchElementException(); // this is the better way. 
        }
        first = first.nextLink;
        return temp;
    }

    //Prints list data
    public void printList() {
        Link currentLink = first;
        System.out.print("List: ");
        while(currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}  

class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();

        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);

        list.printList();

        while(!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("deleted: ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}
220
14.05.2017 14:02:05
Вы также можете довольно легко улучшить этот код, чтобы использовать обобщенные типы для типов данных вместо хранения значений типа int и double.
shsteimer 29.05.2009 13:36:25
@shsteimer: вполне определенно, но так как единственное хорошее использование этого кода - это демонстрация техники, это никому не поможет. Это только рассеет основную идею.
Joachim Sauer 28.12.2009 15:07:42
Это не очень хороший подход к ОО - иметь public Link nextLinkи работать над ним вне класса. Это может быть респектабельным, когда Linkбудет внутренний класс LinkList. Это еще одна связка кода, написанного, поскольку Java была только другой версией c.
Bart 3.09.2010 11:29:51
Когда вы вставляете, ваш первый элемент никогда не получит nextLink - если я что-то упустил из-за ссылок на Java
Chris S 6.03.2011 22:39:48
Как я могу реализовать метод удаления (индекс)?
JohnDow 9.01.2013 14:52:23

Java имеет реализацию LinkedList , которую вы можете попробовать. Вы можете скачать JDK и его источники на java.sun.com .

55
13.08.2008 16:35:02
Разве Java Linkedlist не позволяет вставлять и удалять элементы в произвольных позициях?
Seun Osewa 25.02.2010 17:40:31
Разве это не весь смысл связанного списка?
jrockway 17.05.2010 03:48:44
@ Seun Osewa, если вы хотите добавить в произвольную позицию, пожалуйста, используйте ArrayList :)
headgrowe 28.02.2013 13:41:46
Вместо того, чтобы загружать JDK для просмотра его реализации LinkedList, вы можете просто посмотреть его LinkedList.javaонлайн здесь . На этой странице даже синтаксис выделяет код и визуализирует комментарии Javadoc.
Rory O'Kane 13.12.2013 05:20:32

Используйте java.util.LinkedList . Как это:

list = new java.util.LinkedList()
22
20.08.2008 06:45:06

Гораздо лучше использовать java.util.LinkedList, потому что он, вероятно, гораздо более оптимизирован, чем тот, который вы напишите.

9
27.03.2009 17:14:20
И это будет работать впервые.
Peter Lawrey 29.05.2009 21:33:58

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

public void insert(int d1, double d2) { 
    Link link = new Link(d1, d2); 

    if(first==null){
        link.nextLink = null;
        first = link; 
        last=link;
    }
    else{
        last.nextLink=link;
        link.nextLink=null;
        last=link;
    }
} 
17
28.12.2009 14:44:17
Добавить новый в конце, если не указано иное. :-)
user201788 19.07.2011 18:02:37
//slightly improved code without using collection framework

package com.test;

public class TestClass {

    private static Link last;
    private static Link first;

    public static void main(String[] args) {

        //Inserting
        for(int i=0;i<5;i++){
            Link.insert(i+5);
        }
        Link.printList();

        //Deleting
        Link.deletefromFirst();
        Link.printList();
    }


    protected  static class Link {
        private int data;
        private Link nextlink;

        public Link(int d1) {
            this.data = d1;
        }

        public static void insert(int d1) {
            Link a = new Link(d1);
            a.nextlink = null;
            if (first != null) {
                last.nextlink = a;
                last = a;
            } else {
                first = a;
                last = a;
            }
            System.out.println("Inserted -:"+d1);
        }

        public static void deletefromFirst() {
            if(null!=first)
            {
                System.out.println("Deleting -:"+first.data);
                first = first.nextlink;
            }
            else{
                System.out.println("No elements in Linked List");
            }
        }

        public static void printList() {
            System.out.println("Elements in the list are");
            System.out.println("-------------------------");
            Link temp = first;
            while (temp != null) {
                System.out.println(temp.data);
                temp = temp.nextlink;
            }
        }
    }
}
7
13.07.2011 10:34:26