Concatenation

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

Example

A list consists of the objects. A list consists of the elements.

These two lists are combined into a single list by a concatenation. The order of objects within the sub- lists was not changed.

Graphical representation of

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

Reference

It is important to note that the concatenation that is the pointer meaningful bends (see pseudo-code ), to still have access to the two individual lists until the end. Otherwise it could happen that you can not perform the concatenation correct and receives no access because individual pointers have already been overwritten.

Pseudocode

Line 1 M → next → prev = prev → L Line 2 M → prev → next = L 3rd row L → prev → next = M → next Line 4 L → M → prev = prev For security release the dummy from the list M. Line 5 M → next = NIL Line 6 M → prev = NIL Line 7, M = NIL Although one can compare NIL (Not in List) with an assignment of NULL.

Comments on the pseudo code

Line 1: predecessor is the last object from the list L.

Line 2: Successor of the last object in the list M is the dummy of list L.

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

Line 4: is the predecessor of the dummies the complete list

Line 5: Enable dummy of M, and M itself.

Strings as a special case

• Data structure