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

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

在Java中创建链表的最佳方式是什么?

6 个解决方案

#1

The obvious solution to developers familiar to Java is to use the LinkedList class 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. Enhancements to this implementation include making it a double-linked list, adding methods to insert and delete from the middle or end, and by adding get and sort methods as well.

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

Note: In the example, the Link object doesn't actually contain another Link object - nextLink is 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();
    }
}

#2

Java has a LinkedList implementation, 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及其源代码。

#3

Use java.util.LinkedList. Like this:

使用java.util.LinkedList。是这样的:

list = new java.util.LinkedList()

#4

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

#5

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，因为它可能比你要写的那个优化得多。

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