List (data structure)

from Wikipedia, the free encyclopedia

The linked list is a dynamic data structure that implements ordered storage of data items . The number of objects does not have to be known in advance and remains open for the entire lifetime of the list.

Simply linked lists

The data type of the singly linked lists with elements of type is defined recursively as . The technical implementation usually takes place through individual nodes, which consist of the net data itself and a reference to the successor node. In the last node, the so-called null pointer is specified as the successor node, which is also called.

Elementary list operations are expanding the list by one node at the beginning and removing the first node, which can be done in time.

Singly linked list with three values

advantages

  • When the search is done and the insertion point is found, the effort of inserting is at every point . In an array , however, data records would have to be copied.
  • Little additional memory requirement (1 pointer).

disadvantage

  • The cost of searching is because, in the worst case, it is necessary to iterate over each node.

Applications

Simply linked lists are used in highly dynamic environments in which it is no longer possible to work sensibly with arrays, as they make handling syntactic operations extremely difficult. The simply linked list with data type is denoted by where further elementary LISP data types are, the central data type of the LISP programming language . Even LISP programs are such lists themselves.

Doubly linked list

Doubly linked list with three values

In contrast to the singly linked list, each element has a pointer to both the following and the preceding element.

The predecessor pointer of the first and the successor pointer of the last element point to the value NULL . This particular element is used to determine the beginning and the end of a doubly linked list.

advantages

  • An element can be removed from the list even if the element did not arrive via either of the two concatenations. In this case, the predecessor would have to be searched for in the singly linked list.
  • The list can be iterated from back to front.

disadvantage

  • Higher memory requirements for the additional pointers .
  • When deleting and inserting, the previous pointers of the following list elements must also be adapted.

Other forms

List header

The list header (or list anchor) is a data field that can contain additional information, such as the number of nodes in the list. He points to the first element.

Skip list

As with linked lists, the data is also stored in containers for the skip list . These contain a key and a pointer to the next container. However, containers in ski lists can also contain pointers to other containers that are not directly following. So keys can be skipped. Each container has a certain height h, which is 1 smaller than the number of pointers a container contains. The hands are numbered from 0 to h. A skip list basically imitates the binary search on a field .

Skip list with several jumps

There are three types of types of skip lists:

  1. balanced SkipList
  2. unbalanced SkipList (see picture)
  3. randomized SkipList

Multiple occurrences of the content are permitted for all types. However, the unbalanced and unbalanced SkipLists are ordered, whereas the randomized SkipList need not necessarily be ordered. By adding intermediate stations, which increases the implementation effort, the average access time and the associated complexity can be reduced. An extension of the SkipList principle is the link with the principle of the doubly linked list, which enables "returns". With a balanced SkipList, however, this does not reduce the complexity, whereas with an unbalanced SkipList intermediate stations can be dispensed with, which in turn increases the access to elements in the vicinity of the next intermediate station.

The insert, find, and delete operations each have an expected run time of .

Calculation of the container height

In the case of the randomized skip list, the height h is calculated according to the random principle. The probability of reaching a certain altitude can be determined as follows:

In the case of non-randomized ski lists, the height is determined in such a way that each pointer with pointer height z can point to a container 2 z positions further back in the list - i.e. all containers in between have a lower height than the pointer.

Adaptive lists

Since the effort of accessing an element of a simply linked list increases with the distance from the start per individual step, the principle of adaptive lists was found. In an attempt to keep this effort as low as possible on average, the list elements are sorted according to their access frequency. There are three basic strategies:

  • MoveToFront: Each time an element is accessed, it is removed and inserted at the beginning of the list.
  • Transpose: Each time an element is accessed, it is swapped with its predecessor (special case: first element)
  • Gratification: The access frequency for each element is saved. The list is re-sorted at a certain interval based on the access frequency.

Lists in object-oriented programming

In object-oriented programming , lists are characterized by a number of list operations based on the principle of data encapsulation . Internally, different and also more complicated data structures such as binary trees can be used. Due to the internal data structure, other functions such as sorting, sorted insertion, removal of the largest element, etc. can often be offered.

Depending on the intended use, it can make sense to choose between specific implementations of the list interface . If, for example, the list is mainly accessed randomly via an index, a linked list would be a poor choice, since there n operations are necessary to address the nth element.

Therefore, in addition to the interface, various concrete implementations are often offered in object-oriented libraries. For example, there is java.util.List as an interface in the Java programming language , and java.util.LinkedList and java.util.ArrayList are offered as specific implementations , among others . In C ++ , lists and vectors are implemented in the standard library.

Examples

The following examples are in pseudocode (based on C ). The list contains the Key field (i.e. the key you are looking for) and the Data field (the user data that is behind the key). The example:

  • Give me the lottery numbers for January 1st, 2006 . It is January 1, 2006 , the key and the lottery numbers are the payload.
  • pNext in a node (element) is the pointer to the next element in the list

Add a new element to the list

   FUNKTION insertElement( Datum, Lottozahlen )
   {
      Zeiger *NeuesElement = Speicherallozierung(size(Datum) + size(Lottozahlen));

      WENN (Speicherallozierung erfolgreich)
      {
         Kopieren von Datum und Lottozahlen nach *NeuesElement;
         NeuesElement->pNext = NULL;
         Zeiger *LetztesElement = FindeLetztesElement();

         WENN (Letztes Element gefunden)
         {
            LetztesElement->pNext = NeuesElement;
            return GELUNGEN;
         }
         SONST
         {
            return FEHLER;
         }

      }
      SONST
      {
         return FEHLER;
      }
   }

Find element

   FUNKTION sucheElement( Datum )
   {

      Variable lz = NULL;
      Zeiger *AktuellesElement = ErstesElement();

      WENN (Erstes Element gefunden)
      {
         SOLANGE (lz == NULL UND AktuellesElement != NULL)
         {
            WENN (AktuellesElement->Datum == Datum)
               lz = AktuellesElement->Lottozahlen;
            SONST
               AktuellesElement = AktuellesElement->pNext;
         }

         WENN (lz != NULL)
            return lz;
         SONST
            return FEHLER;
      }
      SONST
      {
         return FEHLER;
      }
   }

Delete element from list

   FUNKTION deleteElement( Datum )
   {
      Zeiger *aktuellesElement = NULL;
      Zeiger *nächstesElement = ErstesElement();

      SOLANGE ( nächstesElement != NULL )
      {
         WENN (nächstesElement->Datum == Datum) // ''zu löschendes Element gefunden''
         {
            WENN ( aktuellesElement != NULL ) // ''wir befinden uns nicht am Listenbeginn''
            {
               WENN ( nächstesElement->pNext != NULL) // ''wir befinden uns nicht am Listenende''
               {
                  aktuellesElement->pNext = nächstesElement->pNext;
                  Lösche nächstesElement;
               }
               SONST // ''wir befinden uns am Listenende''
               {
                  aktuellesElement->pNext = NULL;
                  Lösche nächstesElement;
               }
            }
            SONST // ''wir befinden uns am Listenbeginn''
            {
               WENN ( nächstesElement->pNext != NULL) // ''wir befinden uns nicht am Listenende''
                  Setze Listenbeginn auf nächstesElement->pNext;
               SONST // ''wir befinden uns am Listenende - wir löschen das einzige Element, Liste ist nun leer''
                  Setze Listenbeginn auf NULL;

               Lösche nächstesElement;
            }
         }
         AktuellesElement = nächstesElement;
         nächstesElement = nächstesElement->pNext;
      }
   }

Use of list in object-oriented language

This example shows the uses of a list in C ++ .

#include <iostream>
#include <list>

using namespace std;

...

// Initialisierung
list<int> liste;

// am Anfang einfügen
liste.push_front(4);
liste.push_front(3);

// am Ende anfügen
liste.push_back(5);
liste.push_back(6);

// die Liste enthält 3 4 5 6
// Durchlaufen der Liste
for (auto it = liste.begin(); it != liste.end(); ++it)
{
   cout << *it << " ";
}

// Entfernen aller Zahlen größer als 4
liste.erase(remove_if(liste.begin(), liste.end(), [](int x) { return x > 4; }), liste.end());

// Sortieren
liste.sort();

// Löschen
liste.clear();

See also

Web links

References and comments

  1. a b The use of a guard pointer or sentinel instead of the zero pointer can save a comparison in the search loop.
  2. java.util.List Java API Specification
  3. java.util.LinkedList Java API Specification
  4. java.util.ArrayList Java API Specification