Creazione di una classe LinkedList da zero
Ci è stato dato l'incarico di creare un LinkedList da zero, e non ci sono assolutamente letture date per guidarci su questo compito che causa migranti. Anche tutto online sembra usare solo i metodi e le cose di LinkedList integrati in Java. Ad ogni modo, le liste collegate hanno perfettamente senso quando si usano le cose predefinite di Java, ma crearle da zero non ha alcun senso. Diciamo che ho
public class LinkedList {
private LinkedList next;
private final String word;
// constructor
public LinkedList(String word, LinkedList next) {
this.word = word;
this.next = next;
}
E quindi magicamente abbiamo una lista collegata. Che succede? Come ho creato un linked lista come questa? Come funziona? Dovrei scrivere un metodo append che aggiunge un parametro String word dato alla fine di this linkedlist. Ho provato a guardare il metodo addLast integrato per la classe java linkedlist integrata, ma non mi è di aiuto, dato che non capisco davvero cosa sta succedendo. Qualcuno cura di aiutarmi:)
12 answers
Se stai effettivamente costruendo un sistema reale, allora sì, in genere useresti semplicemente le cose nella libreria standard se ciò di cui hai bisogno è disponibile lì. Detto questo, non pensare a questo come un esercizio inutile. È bene capire come funzionano le cose e comprendere le liste collegate è un passo importante verso la comprensione di strutture di dati più complesse, molte delle quali non esistono nelle librerie standard.
Ci sono alcune differenze tra il modo in cui stai creando un elenco collegato e il modo in cui l'API Java collections lo fa. L'API Collections sta cercando di aderire a un'interfaccia più complicata. L'elenco collegato API Collections è anche un elenco doppiamente collegato, mentre si sta costruendo un elenco collegato singolarmente. Quello che stai facendo è più appropriato per un compito di classe.
Con la tua classe LinkedList, un'istanza sarà sempre un elenco di almeno un elemento. Con questo tipo di configurazione dovresti usare null per quando hai bisogno di una lista vuota.
Pensa a next come "il resto della lista". In effetti, molte implementazioni simili usano il nome " tail "invece di"next".
Ecco un diagramma di un LinkedList contenente 3 elementi:
Si noti che è un oggetto LinkedList che punta a una parola ("Ciao") e un elenco di 2 elementi. L'elenco di 2 elementi ha una parola ("Stack") e un elenco di 1 elemento. Quella lista di 1 elemento ha una parola ("Overflow") e una lista vuota (null). Quindi puoi trattare next come solo un altro elenco che sembra essere un elemento più corto.
Potresti voler aggiungere un altro costruttore che prende solo una stringa e imposta accanto a null. Questo sarebbe per la creazione di un elenco di 1 elementi.
Per aggiungere, si controlla se next è null. Se lo è, crea un nuovo elenco di elementi e imposta next su quello.
next = new LinkedList(word);
Se next non è null, aggiungi invece a next.
next.append(word);
Questo è l'approccio ricorsivo, che è la quantità minima di codice. Puoi trasformarlo in una soluzione iterativa che sarebbe più efficiente in Java*, e non rischierebbe un overflow dello stack con elenchi molto lunghi, ma immagino che il livello di complessità non sia necessario per il tuo incarico.
* Alcune lingue hanno l'eliminazione della chiamata di coda, che è un'ottimizzazione che consente all'implementazione del linguaggio di convertire "chiamate di coda" (una chiamata a un'altra funzione come ultimo passo prima di tornare) in (effettivamente) un "goto". Questo fa sì che tale codice eviti completamente l'uso dello stack, il che lo rende più sicuro (tu impossibile overflow dello stack se non si utilizza lo stack) e in genere più efficiente. Scheme è probabilmente l'esempio più noto di una lingua con questa funzione.
Quello che hai codificato non è un LinkedList, almeno non uno che riconosco. Per questa assegnazione, si desidera creare due classi:
LinkNode
LinkedList
Un LinkNode ha un campo membro per i dati che contiene e un riferimento LinkNode al successivo LinkNode nel LinkedList. Sì, è una struttura di dati autoreferenziale. A LinkedList ha solo un riferimento speciale LinkNode che si riferisce al primo elemento dell'elenco.
Quando si aggiunge un elemento nel LinkedList, si attraversano tutti i LinkNode's fino a quando raggiungi l'ultimo. Questo LinkNode's successivo dovrebbe essere null. Quindi costruisci un nuovo LinkNode qui, imposta il suo valore e aggiungilo a LinkedList.
public class LinkNode {
String data;
LinkNode next;
public LinkNode(String item) {
data = item;
}
}
public class LinkedList {
LinkNode head;
public LinkedList(String item) {
head = new LinkNode(item);
}
public void add(String item) {
//pseudo code: while next isn't null, walk the list
//once you reach the end, create a new LinkNode and add the item to it. Then
//set the last LinkNode's next to this new LinkNode
}
}
Che ne dici di un'implementazione completamente funzionale di un elenco collegato non ricorsivo?
L'ho creato per i miei algoritmi che classifico come trampolino di lancio per ottenere una migliore comprensione prima di passare alla scrittura di una classe di coda doppiamente collegata per un incarico.
Ecco il codice:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedList<T> implements Iterable<T> {
private Node first;
private Node last;
private int N;
public LinkedList() {
first = null;
last = null;
N = 0;
}
public void add(T item) {
if (item == null) { throw new NullPointerException("The first argument for addLast() is null."); }
if (!isEmpty()) {
Node prev = last;
last = new Node(item, null);
prev.next = last;
}
else {
last = new Node(item, null);
first = last;
}
N++;
}
public boolean remove(T item) {
if (isEmpty()) { throw new IllegalStateException("Cannot remove() from and empty list."); }
boolean result = false;
Node prev = first;
Node curr = first;
while (curr.next != null || curr == last) {
if (curr.data.equals(item)) {
// remove the last remaining element
if (N == 1) { first = null; last = null; }
// remove first element
else if (curr.equals(first)) { first = first.next; }
// remove last element
else if (curr.equals(last)) { last = prev; last.next = null; }
// remove element
else { prev.next = curr.next; }
N--;
result = true;
break;
}
prev = curr;
curr = prev.next;
}
return result;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private class Node {
private T data;
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
public Iterator<T> iterator() { return new LinkedListIterator(); }
private class LinkedListIterator implements Iterator<T> {
private Node current = first;
public T next() {
if (!hasNext()) { throw new NoSuchElementException(); }
T item = current.data;
current = current.next;
return item;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
}
@Override public String toString() {
StringBuilder s = new StringBuilder();
for (T item : this)
s.append(item + " ");
return s.toString();
}
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
while(!StdIn.isEmpty()) {
String input = StdIn.readString();
if (input.equals("print")) { StdOut.println(list.toString()); continue; }
if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
break;
}
}
}
Nota: è un'implementazione piuttosto semplice di una lista collegata singolarmente. Il tipo ' T ' è un segnaposto di tipo generico. Fondamentalmente, questo elenco collegato dovrebbe funzionare con qualsiasi tipo che eredita dall'Oggetto. Se lo si utilizza per i tipi primitivi, assicurarsi di utilizzare gli equivalenti di classe nullable (ex 'Integer' per il tipo 'int'). L'ultima variabile non è realmente necessaria tranne che accorcia gli inserimenti al tempo O(1). Le rimozioni sono lente poiché vengono eseguite in tempo O(N), ma consente di rimuovere la prima occorrenza di un valore nell'elenco.
Se vuoi puoi anche esaminare l'implementazione:
- addFirst () - aggiunge un nuovo elemento all'inizio del LinkedList
- removeFirst () - rimuovere il primo elemento dalla LinkedList
- removeLast () - rimuovere l'ultimo elemento dalla LinkedList
- addAll () - aggiungi un elenco / array di elementi alla LinkedList
- removeAll () - rimuovere un elenco / array di elementi dalla LinkedList
- contains () - controlla se la LinkedList contiene un elemento
- contains () - cancella tutti gli elementi nella LinkedList
Onestamente, ci vogliono solo poche righe di codice per fare questa è una lista doppiamente collegata. La differenza principale tra questa e una lista doppiamente collegata è che le istanze di nodo di una lista doppiamente collegata richiedono un riferimento aggiuntivo che punti all'elemento precedente nell'elenco.
Il vantaggio di questo rispetto a un'implementazione ricorsiva è che è più veloce e non devi preoccuparti di inondare lo stack quando attraversi elenchi di grandi dimensioni.
Ci sono 3 comandi per testarlo nel debugger / console:
- Prefisso di un valore per un '+'lo aggiungerà alla lista.
- Il prefisso con un '-' rimuoverà la prima occorrenza dall'elenco.
- Digitando 'print' si stamperà l'elenco con i valori separati da spazi.
Se non hai mai visto gli interni di come funziona uno di questi ti suggerisco di passare attraverso quanto segue nel debugger:
- add () - inserisce un nuovo nodo alla fine o inizializza il primo / ultimo valore se l'elenco è vuoto
- remove () - guida l'elenco dal dall'inizio alla fine. Se trova una corrispondenza rimuove quell'elemento e collega i collegamenti interrotti tra i collegamenti precedente e successivo nella catena. Eccezioni speciali vengono aggiunte quando non vi è alcun collegamento precedente o successivo.
- toString() - utilizza l'iteratore foreach per percorrere semplicemente la catena di elenchi dall'inizio alla fine.
Mentre esistono approcci migliori e più efficienti per elenchi come elenchi di array, capire come l'applicazione attraversa tramite riferimenti / puntatori è parte integrante di capire quante strutture di dati di livello superiore funzionano.
Suggerimento 1: leggere la descrizione delle liste collegate a http://en.wikipedia.org/wiki/Linked_list
Suggerimento 2: l'implementazione Java di LinkedList è una lista doppiamente collegata. La tua è una lista collegata singolarmente. Gli algoritmi non si applicano direttamente.
Anche:
... ma creare [una classe di elenco collegata] da zero non ha alcun senso.
Dipende da quale sia il risultato richiesto del lavoro. Se l'obiettivo è quello di produrre il codice che soddisfa alcuni requisiti funzionali / non funzionali, allora hai ragione. Se l'obiettivo real è di imparare come programmare / progettare API / implementare strutture dati non banali, l'utilità del prodotto finale è quasi del tutto irrilevante.
E quindi magicamente abbiamo una lista collegata
Quello che hai effettivamente è un tipo di dati aperti, che potrebbe essere usato per costruire una (sorta di) lista. Ma non è quello che vuole il tuo insegnante. E questo certamente non sarebbe considerato un utile lista astrazione. Un'astrazione utile includerebbe:
-
Metodi per fare le cose che i programmatori non vogliono dover ripetere più e più volte, e
Un livello di astrazione che impedisce ai programmatori di" rompere " l'elenco; ad esempio creando accidentalmente un ciclo o cucendo accidentalmente una sottolista in due elenchi per creare un albero invertito.
Certo, una lista collegata è un po ' confusa per la programmazione di n00bs, praticamente la tentazione è di guardarla come Bambole russe, perché è quello che sembra, un oggetto LinkedList in un oggetto LinkedList. Ma questo è un tocco difficile da visualizzare, invece guardarlo come un computer.
LinkedList = Dati + prossimo membro
Dove è l'ultimo membro della lista se next è NULL
Quindi un LinkedList di 5 membri sarebbe:
LinkedList (Data1, LinkedList (Data2, LinkedList (Data3, LinkedList (Data4, LinkedList (Data5, NULL)))))
Ma puoi pensarlo semplicemente:
Data1 - > Data2 -> Data3 -> Data4 -> Data5 - > NULL
Quindi, come troviamo la fine di questo? Bene, sappiamo che il NULL è la fine quindi:
public void append(LinkedList myNextNode) {
LinkedList current = this; //Make a variable to store a pointer to this LinkedList
while (current.next != NULL) { //While we're not at the last node of the LinkedList
current = current.next; //Go further down the rabbit hole.
}
current.next = myNextNode; //Now we're at the end, so simply replace the NULL with another Linked List!
return; //and we're done!
}
Questo è un codice molto semplice, ovviamente, e si interromperà all'infinito se gli dai un elenco collegato circolarmente! Ma queste sono le basi.
Programma elenco collegato con le seguenti funzionalità
1 Insert At Start
2 Insert At End
3 Insert At any Position
4 Delete At any Position
5 Display
6 Get Size
7 Empty Status
8 Replace data at given postion
9 Search Element by position
10 Delete a Node by Given Data
11 Search Element Iteratively
12 Search Element Recursively
package com.elegant.ds.linkedlist.practice;
import java.util.Scanner;
class Node {
Node link = null;
int data = 0;
public Node() {
link = null;
data = 0;
}
public Node(int data, Node link) {
this.data = data;
this.link = null;
}
public Node getLink() {
return link;
}
public void setLink(Node link) {
this.link = link;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
class SinglyLinkedListImpl {
Node start = null;
Node end = null;
int size = 0;
public SinglyLinkedListImpl() {
start = null;
end = null;
size = 0;
}
public void insertAtStart(int data) {
Node nptr = new Node(data, null);
if (start == null) {
start = nptr;
end = start;
} else {
nptr.setLink(start);
start = nptr;
}
size++;
}
public void insertAtEnd(int data) {
Node nptr = new Node(data, null);
if (start == null) {
start = nptr;
end = nptr;
} else {
end.setLink(nptr);
end = nptr;
}
size++;
}
public void insertAtPosition(int position, int data) {
Node nptr = new Node(data, null);
Node ptr = start;
position = position - 1;
for (int i = 1; i < size; i++) {
if (i == position) {
Node temp = ptr.getLink();
ptr.setLink(nptr);
nptr.setLink(temp);
break;
}
ptr = ptr.getLink();
}
size++;
}
public void repleaceDataAtPosition(int position, int data) {
if (start == null) {
System.out.println("Empty!");
return;
}
Node ptr = start;
for (int i = 1; i < size; i++) {
if (i == position) {
ptr.setData(data);
}
ptr = ptr.getLink();
}
}
public void deleteAtPosition(int position) {
if (start == null) {
System.out.println("Empty!");
return;
}
if (position == size) {
Node startPtr = start;
Node endPtr = start;
while (startPtr != null) {
endPtr = startPtr;
startPtr = startPtr.getLink();
}
end = endPtr;
end.setLink(null);
size--;
return;
}
Node ptr = start;
position = position - 1;
for (int i = 1; i < size; i++) {
if (i == position) {
Node temp = ptr.getLink();
temp = temp.getLink();
ptr.setLink(temp);
break;
}
ptr = ptr.getLink();
}
size--;
}
public void deleteNodeByGivenData(int data) {
if (start == null) {
System.out.println("Empty!");
return;
}
if (start.getData() == data && start.getLink() == null) {
start = null;
end = null;
size--;
return;
}
if (start.getData() == data && start.getLink() != null) {
start = start.getLink();
size--;
return;
}
if (end.getData() == data) {
Node startPtr = start;
Node endPtr = start;
startPtr = startPtr.getLink();
while (startPtr.getLink() != null) {
endPtr = startPtr;
startPtr = startPtr.getLink();
}
end = endPtr;
end.setLink(null);
size--;
return;
}
Node startPtr = start;
Node prevLink = startPtr;
startPtr = startPtr.getLink();
while (startPtr.getData() != data && startPtr.getLink() != null) {
prevLink = startPtr;
startPtr = startPtr.getLink();
}
if (startPtr.getData() == data) {
Node temp = prevLink.getLink();
temp = temp.getLink();
prevLink.setLink(temp);
size--;
return;
}
System.out.println(data + " not found!");
}
public void disply() {
if (start == null) {
System.out.println("Empty!");
return;
}
if (start.getLink() == null) {
System.out.println(start.getData());
return;
}
Node ptr = start;
System.out.print(ptr.getData() + "->");
ptr = start.getLink();
while (ptr.getLink() != null) {
System.out.print(ptr.getData() + "->");
ptr = ptr.getLink();
}
System.out.println(ptr.getData() + "\n");
}
public void searchElementByPosition(int position) {
if (position == 1) {
System.out.println("Element at " + position + " is : " + start.getData());
return;
}
if (position == size) {
System.out.println("Element at " + position + " is : " + end.getData());
return;
}
Node ptr = start;
for (int i = 1; i < size; i++) {
if (i == position) {
System.out.println("Element at " + position + " is : " + ptr.getData());
break;
}
ptr = ptr.getLink();
}
}
public void searchElementIteratively(int data) {
if (isEmpty()) {
System.out.println("Empty!");
return;
}
if (start.getData() == data) {
System.out.println(data + " found at " + 1 + " position");
return;
}
if (start.getLink() != null && end.getData() == data) {
System.out.println(data + " found at " + size + " position");
return;
}
Node startPtr = start;
int position = 0;
while (startPtr.getLink() != null) {
++position;
if (startPtr.getData() == data) {
break;
}
startPtr = startPtr.getLink();
}
if (startPtr.getData() == data) {
System.out.println(data + " found at " + position);
return;
}
System.out.println(data + " No found!");
}
public void searchElementRecursively(Node start, int data, int count) {
if (isEmpty()) {
System.out.println("Empty!");
return;
}
if (start.getData() == data) {
System.out.println(data + " found at " + (++count));
return;
}
if (start.getLink() == null) {
System.out.println(data + " not found!");
return;
}
searchElementRecursively(start.getLink(), data, ++count);
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return start == null;
}
}
public class SinglyLinkedList {
@SuppressWarnings("resource")
public static void main(String[] args) {
SinglyLinkedListImpl listImpl = new SinglyLinkedListImpl();
System.out.println("Singly Linked list : ");
boolean yes = true;
do {
System.out.println("1 Insert At Start :");
System.out.println("2 Insert At End :");
System.out.println("3 Insert At any Position :");
System.out.println("4 Delete At any Position :");
System.out.println("5 Display :");
System.out.println("6 Get Size");
System.out.println("7 Empty Status");
System.out.println("8 Replace data at given postion");
System.out.println("9 Search Element by position ");
System.out.println("10 Delete a Node by Given Data");
System.out.println("11 Search Element Iteratively");
System.out.println("12 Search Element Recursively");
System.out.println("13 Exit :");
Scanner scanner = new Scanner(System.in);
int choice = scanner.nextInt();
switch (choice) {
case 1:
listImpl.insertAtStart(scanner.nextInt());
break;
case 2:
listImpl.insertAtEnd(scanner.nextInt());
break;
case 3:
int position = scanner.nextInt();
if (position <= 1 || position > listImpl.getSize()) {
System.out.println("invalid position!");
} else {
listImpl.insertAtPosition(position, scanner.nextInt());
}
break;
case 4:
int deletePosition = scanner.nextInt();
if (deletePosition <= 1 || deletePosition > listImpl.getSize()) {
System.out.println("invalid position!");
} else {
listImpl.deleteAtPosition(deletePosition);
}
break;
case 5:
listImpl.disply();
break;
case 6:
System.out.println(listImpl.getSize());
break;
case 7:
System.out.println(listImpl.isEmpty());
break;
case 8:
int replacePosition = scanner.nextInt();
if (replacePosition < 1 || replacePosition > listImpl.getSize()) {
System.out.println("Invalid position!");
} else {
listImpl.repleaceDataAtPosition(replacePosition, scanner.nextInt());
}
break;
case 9:
int searchPosition = scanner.nextInt();
if (searchPosition < 1 || searchPosition > listImpl.getSize()) {
System.out.println("Invalid position!");
} else {
listImpl.searchElementByPosition(searchPosition);
}
break;
case 10:
listImpl.deleteNodeByGivenData(scanner.nextInt());
break;
case 11:
listImpl.searchElementIteratively(scanner.nextInt());
break;
case 12:
listImpl.searchElementRecursively(listImpl.start, scanner.nextInt(), 0);
break;
default:
System.out.println("invalid choice");
break;
}
} while (yes);
}
}
Ti aiuterà nella lista collegata.
Elenco collegato per dimostrare le operazioni Insert Front, Delete Front, Insert Rear e Delete Rear in Java:
import java.io.DataInputStream;
import java.io.IOException;
public class LinkedListTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = null;
DataInputStream reader = new DataInputStream(System.in);
int op = 0;
while(op != 6){
try {
System.out.println("Enter Option:\n1:Insert Front 2:Delete Front 3:Insert Rear 4:Delete Rear 5:Display List 6:Exit");
//op = reader.nextInt();
op = Integer.parseInt(reader.readLine());
switch (op) {
case 1:
System.out.println("Enter Value: ");
int val = Integer.parseInt(reader.readLine());
root = insertNodeFront(val,root);
display(root);
break;
case 2:
root=removeNodeFront(root);
display(root);
break;
case 3:
System.out.println("Enter Value: ");
val = Integer.parseInt(reader.readLine());
root = insertNodeRear(val,root);
display(root);
break;
case 4:
root=removeNodeRear(root);
display(root);
break;
case 5:
display(root);
break;
default:
System.out.println("Invalid Option");
break;
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
System.out.println("Exited!!!");
try {
reader.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static Node insertNodeFront(int value, Node root){
Node temp = new Node(value);
if(root==null){
return temp; // as root or first
}
else
{
temp.next = root;
return temp;
}
}
static Node removeNodeFront(Node root){
if(root==null){
System.out.println("List is Empty");
return null;
}
if(root.next==null){
return null; // remove root itself
}
else
{
root=root.next;// make next node as root
return root;
}
}
static Node insertNodeRear(int value, Node root){
Node temp = new Node(value);
Node cur = root;
if(root==null){
return temp; // as root or first
}
else
{
while(cur.next!=null)
{
cur = cur.next;
}
cur.next = temp;
return root;
}
}
static Node removeNodeRear(Node root){
if(root==null){
System.out.println("List is Empty");
return null;
}
Node cur = root;
Node prev = null;
if(root.next==null){
return null; // remove root itself
}
else
{
while(cur.next!=null)
{
prev = cur;
cur = cur.next;
}
prev.next=null;// remove last node
return root;
}
}
static void display(Node root){
System.out.println("Current List:");
if(root==null){
System.out.println("List is Empty");
return;
}
while (root!=null){
System.out.print(root.val+"->");
root=root.next;
}
System.out.println();
}
static class Node{
int val;
Node next;
public Node(int value) {
// TODO Auto-generated constructor stub
val = value;
next = null;
}
}
}
Come ho creato una linkedlist come questa. Come funziona? Questo è tutto un elenco collegato è. Un elemento con un collegamento all'elemento successivo nell'elenco. Finché si mantiene un riferimento all'elemento all'inizio dell'elenco, è possibile attraversare il tutto utilizzando ogni riferimento successivo al valore successivo.
Per aggiungere, tutto ciò che devi fare è trovare la fine dell'elenco e rendere l'elemento successivo il valore che vuoi aggiungere, quindi se questo ha un valore non nullo, dovresti chiamare aggiungere alla voce successiva fino a trovare la fine della lista.
this.next.Append(word);
Ha appena fatto un riassunto su github implementando LinkedList da zero. Può aiutare. Guarda qui.
Https://gist.github.com/akshaynagpal/14ee8b54cd018bd05b2a3c2432c818dc
Leggere questo articolo: Come implementare una classe LinkedList da zero in Java
package com.crunchify.tutorials;
/**
* @author Crunchify.com
*/
public class CrunchifyLinkedListTest {
public static void main(String[] args) {
CrunchifyLinkedList lList = new CrunchifyLinkedList();
// add elements to LinkedList
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
/*
* Please note that primitive values can not be added into LinkedList
* directly. They must be converted to their corresponding wrapper
* class.
*/
System.out.println("lList - print linkedlist: " + lList);
System.out.println("lList.size() - print linkedlist size: " + lList.size());
System.out.println("lList.get(3) - get 3rd element: " + lList.get(3));
System.out.println("lList.remove(2) - remove 2nd element: " + lList.remove(2));
System.out.println("lList.get(3) - get 3rd element: " + lList.get(3));
System.out.println("lList.size() - print linkedlist size: " + lList.size());
System.out.println("lList - print linkedlist: " + lList);
}
}
class CrunchifyLinkedList {
// reference to the head node.
private Node head;
private int listCount;
// LinkedList constructor
public CrunchifyLinkedList() {
// this is an empty list, so the reference to the head node
// is set to a new node with no data
head = new Node(null);
listCount = 0;
}
public void add(Object data)
// appends the specified element to the end of this list.
{
Node crunchifyTemp = new Node(data);
Node crunchifyCurrent = head;
// starting at the head node, crawl to the end of the list
while (crunchifyCurrent.getNext() != null) {
crunchifyCurrent = crunchifyCurrent.getNext();
}
// the last node's "next" reference set to our new node
crunchifyCurrent.setNext(crunchifyTemp);
listCount++;// increment the number of elements variable
}
public void add(Object data, int index)
// inserts the specified element at the specified position in this list
{
Node crunchifyTemp = new Node(data);
Node crunchifyCurrent = head;
// crawl to the requested index or the last element in the list,
// whichever comes first
for (int i = 1; i < index && crunchifyCurrent.getNext() != null; i++) {
crunchifyCurrent = crunchifyCurrent.getNext();
}
// set the new node's next-node reference to this node's next-node
// reference
crunchifyTemp.setNext(crunchifyCurrent.getNext());
// now set this node's next-node reference to the new node
crunchifyCurrent.setNext(crunchifyTemp);
listCount++;// increment the number of elements variable
}
public Object get(int index)
// returns the element at the specified position in this list.
{
// index must be 1 or higher
if (index <= 0)
return null;
Node crunchifyCurrent = head.getNext();
for (int i = 1; i < index; i++) {
if (crunchifyCurrent.getNext() == null)
return null;
crunchifyCurrent = crunchifyCurrent.getNext();
}
return crunchifyCurrent.getData();
}
public boolean remove(int index)
// removes the element at the specified position in this list.
{
// if the index is out of range, exit
if (index < 1 || index > size())
return false;
Node crunchifyCurrent = head;
for (int i = 1; i < index; i++) {
if (crunchifyCurrent.getNext() == null)
return false;
crunchifyCurrent = crunchifyCurrent.getNext();
}
crunchifyCurrent.setNext(crunchifyCurrent.getNext().getNext());
listCount--; // decrement the number of elements variable
return true;
}
public int size()
// returns the number of elements in this list.
{
return listCount;
}
public String toString() {
Node crunchifyCurrent = head.getNext();
String output = "";
while (crunchifyCurrent != null) {
output += "[" + crunchifyCurrent.getData().toString() + "]";
crunchifyCurrent = crunchifyCurrent.getNext();
}
return output;
}
private class Node {
// reference to the next node in the chain,
// or null if there isn't one.
Node next;
// data carried by this node.
// could be of any type you need.
Object data;
// Node constructor
public Node(Object dataValue) {
next = null;
data = dataValue;
}
// another Node constructor if we want to
// specify the node to point to.
public Node(Object dataValue, Node nextValue) {
next = nextValue;
data = dataValue;
}
// these methods should be self-explanatory
public Object getData() {
return data;
}
public void setData(Object dataValue) {
data = dataValue;
}
public Node getNext() {
return next;
}
public void setNext(Node nextValue) {
next = nextValue;
}
}
}
Uscita
lList - print linkedlist: [1][2][3][4][5]
lList.size() - print linkedlist size: 5
lList.get(3) - get 3rd element: 3
lList.remove(2) - remove 2nd element: true
lList.get(3) - get 3rd element: 4
lList.size() - print linkedlist size: 4
lList - print linkedlist: [1][3][4][5]
Motivi trovare muggito Programma
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListManual {
Node node;
public void pushElement(int next_node) {
Node nd = new Node(next_node);
nd.next = node;
node = nd;
}
public int getSize() {
Node temp = node;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public void getElement() {
Node temp = node;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
public static void main(String[] args) {
LinkedListManual obj = new LinkedListManual();
obj.pushElement(1);
obj.pushElement(2);
obj.pushElement(3);
obj.getElement(); //get element
System.out.println(obj.getSize()); //get size of link list
}
}
class Node
{
int data;
Node link;
public Node()
{
data=0;
link=null;
}
Node ptr,start,temp;
void create()throws IOException
{
int n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter first data");
this.data=Integer.parseInt(br.readLine());
ptr=this;
start=ptr;
char ins ='y';
do
{
System.out.println("Wanna Insert another node???");
ins=(char)br.read();
br.read();
if(ins=='y')
{
temp=new Node();
System.out.println("Enter next data");
temp.data=Integer.parseInt(br.readLine());
temp.link=null;
ptr.link=temp;
temp=null;
ptr=ptr.link;
}
}while(ins=='y');
}
public static void main(String args[])throws IOException
{
Node first= new Node();
first.create();
}
}