Java Language
listor

Introduktion

Syntax

• ls.add (E-element); // Lägger till ett element
• ls.remove (E-element); // Tar bort ett element
• för (E-element: ls) {} // Iterates över varje element
• ls.toArray (ny sträng [ls.length]); // Konverterar en lista med strängar till en rad strängar
• ls.get (int-index); // Returnerar elementet vid det angivna indexet.
• ls.set (int-index, E-element); // Ersätter elementet på en specificerad position.
• ls.isEmpty (); // Returnerar sant om arrayen inte innehåller några element, annars returnerar det falskt.
• ls.indexOf (Objekt o); // Returnerar indexet för den första platsen för det specificerade elementet o, eller, om det inte finns, returnerar -1.
• ls.lastIndexOf (Objekt o); // Returnerar indexet för den sista platsen för det specificerade elementet o, eller, om det inte finns, returnerar -1.
• ls.size (); // Returnerar antalet element i listan.

Anmärkningar

List<String> list = new ArrayList<>();
list.add("world");
System.out.println(list.indexOf("world"));      // Prints "0"
// Inserting a new value at index 0 moves "world" to index 1
list.add(0, "Hello");
System.out.println(list.indexOf("world"));      // Prints "1"
System.out.println(list.indexOf("Hello"));      // Prints "0"

Sortera en generisk lista

Collections erbjuder två statiska standardmetoder för att sortera en lista:

• sort(List<T> list) tillämpliga på listor där T extends Comparable<? super T> och
• sort(List<T> list, Comparator<? super T> c) tillämpliga på listor av vilken typ som helst.

För att tillämpa det förstnämnda krävs ändring av klassen av listelement som sorteras, vilket inte alltid är möjligt. Det kan också vara oönskat eftersom även om det tillhandahåller standardsortering kan andra sorteringsorder krävas under olika omständigheter, eller sortering är bara en engångsuppgift.

Tänk på att vi har en uppgift att sortera objekt som är instanser i följande klass:

public class User {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }
}

För att kunna använda Collections.sort(List<User> list) måste vi ändra User att genomföra Comparable gränssnittet. Till exempel

public class User implements Comparable<User> {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }

    @Override
    /** The natural ordering for 'User' objects is by the 'id' field. */
    public int compareTo(User o) {
        return id.compareTo(o.id);
    }
}

(Bortsett från: många vanliga Java-klasser som String , Long , Integer implementerar det Comparable gränssnittet. Detta gör listor över dessa element som kan sorteras som standard och förenklar implementeringen av compare eller compareTo i andra klasser.)

Med ändringen ovan kan vi enkelt sortera en lista över User objekt baserat på klasserna naturligt beställer. (I det här fallet har vi definierat det för att beställa baserat på id värden). Till exempel:

List<User> users = Lists.newArrayList(
    new User(33L, "A"),
    new User(25L, "B"),
    new User(28L, ""));
Collections.sort(users);

System.out.print(users);
// [B:25, C:28, A:33]

Men anta att vi ville att sortera User med name snarare än genom id . Antag alternativt att vi inte hade kunnat ändra klassen för att göra den implementerbar Comparable .

Det är här sort med Comparator argumentet är användbar:

Collections.sort(users, new Comparator<User>() {
    @Override
    /* Order two 'User' objects based on their names. */
    public int compare(User left, User right) {
        return left.username.compareTo(right.username);
    }
});
System.out.print(users);
// [A:33, B:25, C:28]

Collections.sort(users, (l, r) -> l.username.compareTo(r.username));

users.sort((l, r) -> l.username.compareTo(r.username))

Skapa en lista

Ge din lista en typ

För att skapa en lista behöver du en typ (valfri klass, t.ex. String ). Detta är typen av din List . List lagrar bara objekt av den angivna typen. Till exempel:

List<String> strings;

Kan lagra "string1" , "hello world!" , "goodbye" osv, men det kan inte lagra 9.2 , men:

List<Double> doubles;

Kan lagra 9.2 , men inte "hello world!" .

Initiera din lista

Om du försöker lägga till något i listorna ovan får du en NullPointerException, eftersom strings och doubles båda lika noll !

Det finns två sätt att initialisera en lista:

Alternativ 1: Använd en klass som implementerar Lista

List är ett gränssnitt, vilket betyder att det inte finns en konstruktör, snarare metoder som en klass måste åsidosätta. ArrayList är den mest använda List , även om LinkedList är vanligt. Så vi initialiserar vår lista så här:

List<String> strings = new ArrayList<String>();

eller

List<String> strings = new LinkedList<String>();

List<String> strings = new ArrayList<>();

List<String> strings = new LinkedList<>();

Alternativ 2: Använd klassen Samlingar

Den Collections klass ger två användbara metoder för att skapa listor utan List variabel:

• emptyList() : returnerar en tom lista.
• singletonList(T) : skapar en lista över typ T och lägger till det angivna elementet.

Och en metod som använder en befintlig List att fylla i data:

• addAll(L, T...) : lägger till alla specificerade element i listan som skickas som den första parametern.

Exempel:

import java.util.List;
import java.util.Collections;

List<Integer> l = Collections.emptyList();
List<Integer> l1 = Collections.singletonList(42);
Collections.addAll(l1, 1, 2, 3);

Verksamhet för positionell åtkomst

List API har åtta metoder för positioneringsåtkomstoperationer:

• add(T type)
• add(int index, T type)
• remove(Object o)
• remove(int index)
• get(int index)
• set(int index, E element)
• int indexOf(Object o)
• int lastIndexOf(Object o)

Så om vi har en lista:

List<String> strings = new ArrayList<String>();

Och vi ville lägga till strängarna "Hej värld!" och "adjö värld!" för det skulle vi göra det som sådant:

strings.add("Hello world!");
strings.add("Goodbye world!");

Och vår lista skulle innehålla de två elementen. Låt oss nu säga att vi ville lägga till "Program börjar!" längst fram på listan. Vi skulle göra detta så här:

strings.add(0, "Program starting!");

OBS: Det första elementet är 0.

Om vi ville ta bort "Goodbye world!" linje, vi kunde göra det så här:

strings.remove("Goodbye world!");

Och om vi ville ta bort den första raden (som i detta fall skulle vara "Programmet startar!", Kunde vi göra det så här:

strings.remove(0);

Notera:

1. Lägga till och ta bort listelement modifierar listan, och detta kan leda till en ConcurrentModificationException om listan uppdateras samtidigt.

2. Lägga till och ta bort element kan vara O(1) eller O(N) beroende på listklassen, metoden som används och om du lägger till / tar bort ett element i början, slutet eller i mitten av listan.

För att hämta ett element i listan på en specificerad position kan du använda E get(int index); metoden för List API. Till exempel:

strings.get(0);

returnerar det första elementet i listan.

Du kan ersätta valfritt element på en specificerad position genom att använda set(int index, E element); . Till exempel:

strings.set(0,"This is a replacement");

Detta ställer in strängen "This is a ersättare" som det första elementet i listan.

Obs: Den inställda metoden kommer att skriva över elementet i position 0. Det kommer inte att lägga till den nya strängen i position 0 och skjuta den gamla till position 1.

int indexOf(Object o); returnerar positionen för den första förekomsten av objektet som skickats som argument. Om det inte finns några förekomster av objektet i listan returneras -1-värdet. I fortsättning på föregående exempel om du ringer:

strings.indexOf("This is a replacement")

0 förväntas returneras när vi ställer strängen "Detta är en ersättning" i position 0 på vår lista. Om det finns mer än en händelse i listan när int indexOf(Object o); kallas då som nämns index kommer den första händelsen att returneras. Genom att ringa int lastIndexOf(Object o) du hämta indexet för den sista händelsen i listan. Så om vi lägger till en ny "Detta är en ersättning":

strings.add("This is a replacement");
strings.lastIndexOf("This is a replacement");

Den här gången kommer 1 att returneras och inte 0;

Iterera över element i en lista

Till exempel kan vi säga att vi har en lista över typsträngar som innehåller fyra element: "hej", "hur", "är", "du?"

Det bästa sättet att iterera över varje element är att använda en för varje slinga:

public void printEachElement(List<String> list){
    for(String s : list){
        System.out.println(s);
    }
}

Vilket skulle skriva ut:

hello,
how
are
you?

För att skriva ut alla på samma rad kan du använda en StringBuilder:

public void printAsLine(List<String> list){
    StringBuilder builder = new StringBuilder();
    for(String s : list){
        builder.append(s);
    }
    System.out.println(builder.toString());
}

Skriver ut:

hello, how are you?

Alternativt kan du använda elementindexering (som beskrivs i Accessing element at ith Index från ArrayList ) för att iterera en lista. Varning: detta tillvägagångssätt är ineffektivt för länkade listor.

Ta bort element från lista B som finns i lista A

Låt oss anta att du har 2 listor A och B, och du vill ta bort alla B- element från A i metoden i detta fall är

 List.removeAll(Collection c);

#Exempel:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));
    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);

    numbersB.removeAll(numbersA);
    System.out.println("B cleared: " + numbersB);
    }

detta kommer att skrivas ut

A: [1, 3, 4, 7, 5, 2]

B: [13, 32, 533, 3, 4, 2]

B rensad: [13, 32, 533]

Hitta vanliga element mellan två listor

Anta att du har två listor: A och B, och du måste hitta de element som finns i båda listorna.

Du kan göra det genom att bara använda metoden List.retainAll() .

Exempel:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));

    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);
    List<Integer> numbersC = new ArrayList<>();
    numbersC.addAll(numbersA);
    numbersC.retainAll(numbersB);

    System.out.println("List A : " + numbersA);
    System.out.println("List B : " + numbersB);
    System.out.println("Common elements between A and B: " + numbersC);

}

Konvertera en lista med heltal till en lista med strängar

List<Integer> nums = Arrays.asList(1, 2, 3);
List<String> strings = nums.stream()
    .map(Object::toString)
    .collect(Collectors.toList());

Det är:

1. Skapa en ström från listan
2. Kartlägga varje element med hjälp av Object::toString
3. Samla String i en List med Collectors.toList()

Skapa, lägga till och ta bort element från en ArrayList

ArrayList är en av de inbyggda datastrukturerna i Java. Det är en dynamisk matris (där storleken på datastrukturen inte behövs förklaras först) för att lagra element (objekt).

Det sträcker sig AbstractList klass och redskap List gränssnitt. En ArrayList kan innehålla duplicerade element där den upprätthåller införingsordningen. Det bör noteras att klassen ArrayList är synkroniserad, så man bör vara försiktig när man hanterar samtidighet med ArrayList . ArrayList tillåter slumpmässig åtkomst eftersom array fungerar på indexbasen. Manipulationen går långsamt i ArrayList grund av förändringar som ofta inträffar när ett element tas bort från matrislistan.

En ArrayList kan skapas enligt följande:

List<T> myArrayList = new ArrayList<>();

Där T ( Generics ) är den typ som lagras i ArrayList .

ArrayList kan vara valfritt objekt. Typen kan inte vara en primitiv typ (använd deras omslagsklasser istället).

För att lägga till ett element i ArrayList använder du metoden add() :

myArrayList.add(element);

Eller för att lägga till objekt i ett visst index:

myArrayList.add(index, element); //index of the element should be an int (starting from 0)

För att ta bort ett objekt från ArrayList använder du metoden ArrayList remove() :

myArrayList.remove(element);

Eller ta bort ett objekt från ett visst index:

myArrayList.remove(index); //index of the element should be an int (starting from 0)

Byte av ett listelement på plats

Detta exempel handlar om att ersätta en List elementet och samtidigt säkerställa att ersättningselementet är vid samma position som det element som skall ersättas.

Detta kan göras på följande sätt:

• set (int-index, T-typ)
• int indexOf (T-typ)

ArrayList en ArrayList innehåller elementen "Program som startar!", "Hej värld!" och "adjö värld!"

List<String> strings = new ArrayList<String>();
strings.add("Program starting!");
strings.add("Hello world!");
strings.add("Goodbye world!");

Om vi känner till indexet för elementet vi vill ersätta kan vi helt enkelt använda set enligt följande:

strings.set(1, "Hi world");

Om vi inte känner till indexet kan vi söka efter det först. Till exempel:

int pos = strings.indexOf("Goodbye world!");
if (pos >= 0) {
    strings.set(pos, "Goodbye cruel world!");
}

Anmärkningar:

1. Den set operationen orsakar inte en ConcurrentModificationException .
2. Den set operationen är snabb ( O(1) ) för ArrayList men långsam ( O(N) ) för en LinkedList .
3. En indexOf sökning på en ArrayList eller LinkedList går långsamt ( O(N) ).

Att göra en lista omodifierbar

Samlingsklassen ger ett sätt att göra en lista omodifierbar:

List<String> ls = new ArrayList<String>();
List<String> unmodifiableList = Collections.unmodifiableList(ls);

Om du vill ha en omodifierbar lista med ett objekt kan du använda:

List<String> unmodifiableList = Collections.singletonList("Only string in the list");

Flytta objekt runt i listan

I klasserna Samlingar kan du flytta objekt runt i listan med olika metoder (det är listan):

Omvända en lista:

Collections.reverse(ls);

Roterande positioner för element i en lista

Rotationsmetoden kräver ett heltalargument. Det är så många platser att flytta den längs linjen förbi. Ett exempel på detta är nedan:

List<String> ls = new ArrayList<String>();
ls.add(" how");
ls.add(" are");
ls.add(" you?");
ls.add("hello,");
Collections.rotate(ls, 1);

for(String line : ls) System.out.print(line);
System.out.println();

Detta kommer att skriva ut "hej, hur mår du?"

Blanda element runt i en lista

Med samma lista ovan kan vi blanda elementen i en lista:

Collections.shuffle(ls);

Vi kan också ge det ett java.util.Random-objekt som det använder för att slumpmässigt placera objekt på platser:

Random random = new Random(12); 
Collections.shuffle(ls, random);

Klasser som implementerar Lista - För- och nackdelar

Den List gränssnittet genomförs av olika klasser. Var och en av dem har sitt eget sätt att implementera det med olika strategier och ge olika fördelar och nackdelar.

Klasser som implementerar lista

Dessa är alla de public klasserna i Java SE 8 som implementerar java.util.List gränssnittet:

1. Abstrakta klasser:
   • AbstractList
   • AbstractSequentialList
2. Betongklasser:
   • Arraylist
   • Attribute
   • CopyOnWriteArrayList
   • Länkad lista
   • RoleList
   • RoleUnresolvedList
   • Stack
   • Vektor

Fördelar och nackdelar med varje implementering i tidskomplexitet

Arraylist

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList är en storlek som kan ändras med storleksanpassning av listgränssnittet. Lagring av listan i en array, Arraylist tillhandahåller metoder (utöver de metoder som genomför Lista gränssnittet) för att manipulera storleken på matrisen.

Initiera ArrayList med heltal med storlek 100

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

- FÖRDELAR:

Storleken, isEmpty, get , set , iterator och listIterator-operationerna körs i konstant tid. Så att få och ställa in varje element i listan har samma tidskostnad :

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

- NACKDELAR:

Att implementeras med en matris (statisk struktur) som lägger till element över storleken på matrisen har en stor kostnad på grund av det faktum att en ny tilldelning måste göras för hela matrisen. Men från dokumentation :

Tilläggsoperationen körs i amorterad konstant tid, det vill säga att lägga till n-element kräver O (n) -tid

Att ta bort ett element kräver O (n) -tid.

Attribute

När kommer

CopyOnWriteArrayList

När kommer

Länkad lista

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList implementeras av en dubbelkopplad lista en länkad datastruktur som består av en uppsättning sekvensiellt länkade poster som kallas noder.

Initiera LinkedList of Integer

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- FÖRDELAR:

Att lägga till eller ta bort ett element framtill på listan eller till slutet har konstant tid.

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- Nackdelar: Från dokumentation :

Åtgärder som indexeras i listan kommer att korsa listan från början eller slut, beroende på vad som är närmare det angivna indexet.

Verksamheter som:

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

RoleList

När kommer

RoleUnresolvedList

När kommer

Stack

När kommer

Vektor

När kommer