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

Question

如何在Java中创建链表？

- Lance Fisher

---

最好的制作链表的方法是使用内置的链表，不要重新编写已经存在的类。 - Peter Lawrey

这个问题是合法的，对于程序员的讨论非常有建设性。 - anshulkatta

Answer 1

对于熟悉Java的开发者而言，显而易见的解决方案是使用已经提供在java.util中的LinkedList类。然而，假设你想出于某些原因自己实现一个链表，这里有一个快速示例：它在列表开头插入新的链接，从列表开头删除，循环遍历列表并打印其中包含的链接。此实现的增强功能包括将其改为双向链表，添加方法以从中间或末尾插入和删除，以及添加获取和排序方法。

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

- Kamikaze Mercenary

---

你也可以很容易地改进这段代码，使用泛型来存储数据类型，而不是存储int和double。 - shsteimer

@shsteimer说：可以肯定地说，但由于这段代码的主要用途是演示技巧，所以它并不能帮助任何人。它只会传播基本思想。 - Joachim Sauer

在类外直接操作public Link nextLink并不是一个好的面向对象编程方法。如果Link是LinkList的内部类，这样做就较为合理。这似乎是在Java还只是C语言的又一堆代码。 - Bart

当您插入时，您的第一项将永远不会获得nextLink - 除非我在Java引用方面漏掉了什么。 - Chris S

如何实现 delete(index) 方法？ - JohnDow

如果你从一个空列表中删除，你会得到一个NullPointerException，具体来说是当你尝试访问first.nextLink时。 - Bad Request

Answer 2

Java拥有一个LinkedList实现，你可能会想要查看。你可以在java.sun.com下载JDK及其源代码。

- david

---

Java的LinkedList不允许在任意位置插入和删除元素吗？ - Seun Osewa

链表的整个意义难道不就在于此吗？ - jrockway

@Seun Osewa 如果您想在任意位置添加，请使用 ArrayList :) - headgrowe

不必下载JDK以查看其对LinkedList的实现，您可以在此在线查看其LinkedList.java（http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/LinkedList.java）。该页面甚至高亮显示代码并内联呈现Javadoc注释。 - Rory O'Kane

Answer 3

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

list = new java.util.LinkedList()

- Juha

Answer 4

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

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

- arnab sarkar

---

除非另有说明，否则在末尾添加新内容。 :-) - user201788

Answer 5

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

- Darth

---

它将一次性成功运行。 - Peter Lawrey

Answer 6

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

- Anitha A