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

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

用Java创建链接列表的最佳方法是什么？

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

注意：在示例中，Link对象实际上并不包含另一个Link对象-nextLink实际上只是对另一个链接的引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

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

Java具有LinkedList实现，您可能想签出。您可以从java.sun.com下载JDK及其源。

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

1	list = new java.util.LinkedList()

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

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