Implement a list as an abstract data type List, where a list is an ordered collection of none or more elements. In a traditional programming language such as C, a list typically is implemented either as an array or as a linked-list, with shortcomings in either implementation: an arrays size must be fixed at definition time, and a linked-list usually requires that the user manipulate pointers. By contrast, the user of a List should need to know only the public interface, which supports the following operations:

Create a list of none or more elements.

Destroy a list.

Insert an item into a specified spot in the list.

Remove one or more items from a list.

Concatentate two or more lists to create a new list.

Divide a list into two or more sublists.

Copy a list.