Lists are sequences of objects, where the basic operations are adding, removing, and iterating over elements.
Linked Lists are sequences where each node contains a pointer to the next node. Finding nodes is O(n) for lists of size n, however adding and removing nodes after a given existing node is O(1). There is the downside that linked lists do not preserve locality among nodes in memory.
Vectors, or Dynamic Arrays, are sequences of continuous fixed-sized chunks. Naive search for nodes is O(n) for lists of size n, however bisect search on sorted vectors is O(log(n)) as the position of each node is easily calculable. Vectors also preserve locality of data in memory. However, insertions and deletions on arbitrary nodes takes O(n) time, as the expected number of nodes to move is n/2. Pushing and popping from the end of vectors is fairly quick, however.
Each c source file is a small standalone program to demonstrate adding and removing text records to list implementations. The input is newline delimited text read from stdin, and EOF (ctrl-d) terminated. Each line should start with a plus or minus.
To add a text string to the list, enter "+<text>". To remove an entry, enter "-<text>".
| Language | Source | Description |
|---|---|---|
| C | file | Simple unsorted linked list |
| C | file | Sorted linked list |
| C | file | Vector list |
| C | file | Sorted vector list |