Concatenation (lists)

The concatenation is an operation on list-like data structures . A list consists of a sequence of objects in a defined order. A concatenation consists of combining two lists into a single list without changing the order of the elements. The first part of the newly joined list is formed by the first argument list, the second part by the second argument list.

example

A list consists of the objects . A list consists of the elements . ${\ displaystyle L}$ ${\ displaystyle l_ {1}, l_ {2}, \ dotsc, l_ {i}}$ ${\ displaystyle M}$ ${\ displaystyle m_ {1}, m_ {2}, \ dotsc, m_ {j}}$

A concatenation merges these two lists into a single list . The order of the objects within the sublists was not changed. ${\ displaystyle L \ circ M = l_ {1}, l_ {2}, \ dotsc, l_ {i}, m_ {1}, m_ {2}, \ dotsc, m_ {j}}$

Graphical representation

An object

The pictures show how an object, the list L and the list M are represented graphically.

List L

List M

Note

When concatenating, it is important to note that the pointers are sensibly bent (see pseudocode) so that you can still access both individual lists until the end. Otherwise it could happen that the concatenation is not carried out correctly and that access is no longer given because individual pointers have already been overwritten.

Pseudocode

Zeile 1. M  → next → prev = L → prev
Zeile 2. M  → prev → next = L
Zeile 3. L  → prev → next = M → next
Zeile 4. L  → prev        = M → prev

Zur Sicherheit den Dummy der Liste M freigeben.
Zeile 5. M → next = NIL
Zeile 6. M → prev = NIL
Zeile 7. M = NIL

Whereby one can compare NIL (Not in List) with the assignment of NULL.

Comments on the pseudocode

Line 1: The predecessor of is the last object from the list L. ${\ displaystyle m_ {1}}$

Line 2: The successor to the last object in list M is the dummy in list L.

Line 3: Successor to the last object in list L is the first in list M.

Line 4: is the predecessor of the dummy in the complete list ${\ displaystyle m_ {j}}$

Line 5: Dummy of M, and M release itself.

List after concatenation

Character strings as a special case

A frequent special case is the concatenation ( concatenation ) of character strings . In this case the lists consist of individual characters and are combined into a single character string. The two character strings "Wiki" and "pedia" can be combined to form the character string "Wikipedia" by means of concatenation.