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

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

Очевидным решением для разработчиков, знакомых с Java, является использование classа LinkedList, уже представленного в java.util . Скажем, однако, вы хотели сделать свою собственную реализацию по какой-то причине. Ниже приведен краткий пример связанного списка, который вставляет новую ссылку в начале списка, удаляет ее с начала списка и перебирает список, чтобы распечатать ссылки, содержащиеся в нем. Усовершенствования этой реализации include в себя создание двойного списка , добавление методов для вставки и удаления из середины или конца, а также добавление методов 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(); } } 

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

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

 list = new java.util.LinkedList() 

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

 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, потому что он, вероятно, гораздо более оптимизирован, чем тот, который вы напишете.

 //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; } } } } 
Давайте будем гением компьютера.