Linked list
The linked list is a dynamic data structure which permits a storage of interrelated objects. The number of objects is not determined in advance. The list is implemented by pointers to each of the following node (s) or memory cells of the memory.
Unlike lists are linear trees, ie an element has exactly one successor. A list can be closed to a cycle (cyclic list ) by the pointer of the last list element is changed so that it points to any list item. This list item (and only this ) then has two predecessors, all other elements have exactly one predecessor. Whether a list is cyclic or not can be determined efficiently with the hare - hedgehog algorithm.
- 3.1 Singly linked list 3.1.1 expansion
- 3.3.1 List with list head
- 3.3.2 Skip List
- 3.3.3 Adaptive lists
- 6.1 Inserting New Item in List
- Search 6.2 element
- 6.3 Deleting item from list
- 6.4 Use of list of object-oriented language
Comparison with other data structures
Arrays
Unlike arrays, the individual memory cells need not be sequentially stored in memory, so it can not be worked with simple address arithmetic, but the locations must be absolute referenced. The advantage of a list over an array is that the insertion and deletion of elements at each point in the list in constant time is possible. This is because only references are reset and not - as in arrays - all following elements must be moved. However, the list uses more memory because the references must be stored on other list items.
Speed of lists in practice
This advantage of lists over arrays is theoretically correct, but often not the case in practice. When insertion and deletion operations are to take place at random positions, where lists could play their advantage of constant time, the correct position must be found in the data structure. Theoretically search operations are equally fast in lists and arrays, that is, the time increases linearly with the size of the data structure. However, in practice, the insertion and deletion run in large arrays from much faster because the data structure is always stored in a non- fragmented form in memory. Lists, however, are modeled in theory than ideal subordinate, while distributing the list items in the reality throughout the storage area. Due to this fragmentation, the number of cache misses increases significantly.
Node
A node ( engl. node) denotes an element of the list containing the data and a pointer to its successor.
Types
A basic distinction between single and multiple or doubly-linked lists.
Singly linked list
It is the simplest kind of linked list because it only has a "start " pointer next to each node. This points to the first node in the list. The last node in the list points to NULL ( NIL here for " Not In List" ).
Verbal definition: A list is either empty or it consists of a head and a pointer, which in turn is a list.
Benefits
- Elements can be quickly inserted at the beginning of the list; very low memory requirements
- Unlike an array insertion is easily possible without the complete record must be copied at any magnification
Disadvantages
- It is time-consuming to search for data, insert node, delete and sort the list, as gone over every single element ( iterated ) be and the insertion of the first and the last digit must be treated separately.
Extension
Since the aforementioned variant has proved to be too cumbersome (see cons ), a pointer to the last element is introduced as an extension. Since you at the end of the list the last element needs to attach, to point to the new elements, one can thus quickly append elements. In the normal, singly linked list you would otherwise have to take the first item and go through to the last. The disadvantage is the effect of a slightly larger memory footprint, because you have to store a pointer to the last element.
Double (multiple) linked list
In contrast to the single- linked list, each element has both a pointer to the following as well as on the previous item.
The predecessor pointer of the first and the successor pointer of the last element point to NULL. This particular element is used to find the beginning and end of a doubly linked list.
Benefits
- The elements in the second half of a sorted list are locate quickly.
- Quick deletion and insertion of elements. This makes, for example, the efficient sorting of the list possible.
Disadvantages
- Higher memory requirement for the additional pointers.
Other forms
List list with head
The list header or sentinel is a special node on the top of the list of additional information such as the number of nodes in the list. The main advantage is that the insertion of the first element is not a special case.
Skip List
Like linked lists, the data is also stored in the skip list in containers. These contain a key and a pointer to the next container. However, containers can contain in skip lists and pointers to other containers, which do not follow directly. It can be skipped so key. Each container has a certain height h which is smaller by 1 than the number of pointers, which contains a container. The pointers are numbered from 0 to h. Basically, a skip list so mimics the Binary Search on a field.
When the skip lists, there are three kinds of types:
In all types, the multiple occurrence of the contents is permitted. However, the training and the unbalanced Skiplist are ordered, whereas the randomized Skiplist not necessarily have to be ordered. By inserting intermediate stations, which increases the cost of implementation, can be reduced the average access time ( and the associated complexity). An extension of the Skip List- principle is the link to the principle of the doubly linked list, which allows the possibility of a " jump back ". In a balanced Skiplist however, this does not reduce the complexity, whereas can be dispensed with an unbalanced Skiplist on intermediate stations, which in turn then increased to access items near the next stop.
The operations Insert, Search and Delete have an expected life of each.
Calculation of container height
In the randomized skip list to calculate the height h is done randomly. The probability that a given level is reached, can be determined as follows:
In non-randomized skip lists the height is determined such that each pointer with pointer to a container height z 2z positions can continue to show in the list at the back - so all containers between a lower height than the pointer.
Adaptive lists
As the effort increases the access to an element of a singly linked list with the distance from start to n steps, they came up with the principle of adaptive lists. This principle is based on the premise of increasing access effort and sorts the list elements according to their access frequency ( sorted past ). There are three basic strategies:
- MoveToFront: On each access to an element, it is removed and inserted at the beginning of the list.
- Transpose: On each access to an element, it is swapped with its predecessor (special case: 1 item )
- Gratification: For each element whose access frequency to be stored. In a certain interval, the list is re- sorted based on the access frequency.
Lists in object-oriented programming
In object-oriented programming, lists are characterized according to the principle of encapsulation by a set of list operations. Intern can be deployed in this different and quite more complicated data structures such as binary trees. Due to the internal data structure, other functions, such as sorting, sorted paste, removing the largest element, etc. can be offered often.
Depending on the application, it may be useful to choose between concrete implementations of the interface list. For example, to access main optionally using an index to the list, a linked list would be a poor choice, since there n operations are required in order to address the n- th element.
Therefore, in object-oriented libraries in addition to the interface different concrete implementations are often offered. For example, there are in the Java programming language as an interface java.util.List, and there are java.util.LinkedList among others and Java.util.ArrayList offered as concrete implementations. Lists and vectors are implemented in the standard library in C .
Lists in the programming language LISP
Lists are in addition to the individual values ( atoms), the basic data structure of the programming language LISP. Also, programs are there lists of lists.
Examples
The following are examples in pseudo code (at C ajar ). There are in the list, the Key field (ie the key that you are looking for ) and the Data field ( the user data to be behind the key ). The sample:
- Give me the lottery numbers from 1 January 2006. It is 1 January 2006, the key and the lottery numbers are the user data.
- PNext in a node ( element ) is the pointer to the next element in the list
Insert new item in list
FUNCTION insert element (date, lottery numbers ) { Pointer * New element = memory allocation (size ( Date ) size ( lottery numbers ) ); IF ( memory allocation succeeded) { Copy date and lottery numbers for * New element; New item -> pNext = NULL; Pointer * Last element = Find Last Element (); IF ( Last element found) { Last Element-> pNext = new element; return SUCCEED; } ELSE { return ERROR; } } ELSE { return ERROR; } } Search element
FUNCTION seeking element (date) { Variable lz = NULL; * Current pointer element = first element (); IF ( First element found) { WHILE ( lz == NULL AND Current item! = NULL) { IF ( Current Element-> date == date) lz = Current Element-> lotto numbers; ELSE Current element = Current Element-> pNext; } IF ( lz! = NULL) return lz; ELSE return ERROR; } ELSE { return ERROR; } } Delete item from list
FUNCTION DeleteElement (date) { Pointer * current element = NULL; Pointer * next element = first element (); WHILE (next element! = NULL) { IF ( next element-> date == date) / /'' to erase element found '' { IF ( current element! = NULL) / /'' we are not on the list first '' { IF ( next element-> pNext! = NULL) / /'' we are not at the bottom of the list '' { current element-> next = pNext element-> pNext; Delete next element; } ELSE / /'' we are at the bottom of the list '' { current element-> pNext = NULL; Delete next element; } } ELSE / /'' we are at the beginning of '' List { IF ( next element-> pNext! = NULL) / /'' we are not at the bottom of the list '' Set list beginning on next element-> pNext; ELSE / /'' we are at the end of the list - we delete the only element that list is now empty '' Set list beginning to NULL; Delete next element; } } Current element = next element; next next element = element-> pNext; } } Using List in object-oriented language
This example illustrates the uses of a list in C .
# include
using namespace std;
...
/ / Initialization
list
- Introduction to linked lists (English)
- Tutorial on linked lists in C # ( English)