如何在 Java 中创建链表数据结构？

How do I create a Linked List Data Structure in Java?

提问by Lance Fisher

What's the best way to make a linked list in Java?

在 Java 中制作链表的最佳方法是什么？

采纳答案by Aaron

The obvious solution to developers familiar to Java is to use the LinkedListclass already provided in java.util. Say, however, you wanted to make your own implementation for some reason. Here is a quick example of a linked list that inserts a new link at the beginning of the list, deletes from the beginning of the list and loops through the list to print the links contained in it. Enhancementsto this implementation include making it a double-linked list, adding methods to insertand deletefrom the middle or end, and by adding getand sortmethods as well.

对于熟悉 Java 的开发人员来说，显而易见的解决方案是使用java.util 中已经提供的LinkedList类。但是，假设您出于某种原因想要制作自己的实现。这是一个链表的快速示例，它在列表的开头插入一个新链接，从列表的开头删除并循环遍历列表以打印其中包含的链接。此实现的增强包括使其成为双链表，添加从中间或末尾插入和删除的方法，以及添加get和sort方法。

Note: In the example, the Link object doesn't actually contain another Link object - nextLinkis actually only a reference to another link.

注意：在示例中，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();
    }
}

回答by dlinsin

Java has a LinkedListimplementation, that you might wanna check out. You can download the JDK and it's sources at java.sun.com.

Java 有一个LinkedList实现，您可能想查看一下。您可以从java.sun.com下载 JDK 及其源代码。

回答by Juha Syrj?l?

Use java.util.LinkedList. Like this:

使用java.util.LinkedList。像这样：

list = new java.util.LinkedList()

回答by Jakub Arnold

Its much better to use java.util.LinkedList, because it's probably much more optimized, than the one that you will write.

使用 java.util.LinkedList 会好得多，因为它可能比您将要编写的要优化得多。

回答by arnab sarkar

The above linked list display in opposite direction. I think the correct implementation of insert method should be

上面的链表反方向显示。我认为插入方法的正确实现应该是

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;
    }
} 

回答by Anitha A

//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;
            }
        }
    }
}