DinS          Written on 2017/4/24

1. Visually, what is a list(列表)?

See featured image above.

List is good at dynamic operations, such as insert and delete, which need only O(1) time. As a cost, however, list needs O(n) to access certain element.

As can be seen, list is composed of several listnodes. Inside nodes there are predecessor, successor and real data. Predecessor and successor are pointers that point to its neighbors so that we can move from one node to another without losing our way. There are two special nodes at front and rear, header and trailer. These mark the begin and end of list. If we move to either, we need to stop because the pred of header and succ of trailer point to null pointer. We can’t get anywhere.

2. Access

List follows call-by-position, or call-by-link. That is to say if we want to access certain element, we need to start from header or trailer and move through pred or succ to get there. In the worst case we need to move n times to get to where we want, which yields O(n).

We can make use of data locality and move frequently used nodes to front or rear to alleviate the high access cost. This, however, won’t change the O(n) fact.

e.g. access the second node from header

First start from header.

Second move to next position through succ.

Third repeat the same procedure to get to the second node and access its data.

You may wonder why can’t we access the second node instantly. Unlike vector whose elements lie in a continuous block, the nodes of list are lost in the vast sea of memory. We only know where header and trailer are, and we need the pointers to move step by step. But the good news is once we get to certain element, we can save the pointer for later use. Thus we don’t need to start again to access the same element.

3. Insert

Inserting a node to a list only affects neighboring nodes, which means this operation is unaffected by the size of list. This gives O(1) time, if we don’t consider the time used to get to certain node.

The procedure is as follows.

First we have a new node and two existing nodes.

Second we wire the pred and succ of the new node to existing nodes.

Third we wire the succ and pred of existing nodes to our new node.

A word of caution: the order of steps matters. It depends on which node is your current node. If the current node is the right node, you need to first make the succ connection, then pred connection. If you reverse the order and first make the pred change, you will lose the way to the left node. If the current node is the left node, first change the pred, and then succ.

4. Delete

Deletion is basically the same as insertion, and needs only O(1) time.

The procedure is as follows.

First we have three nodes and want to delete the middle node.

Second we wire the succ of left node and pred of right node.

At this point we will never get to the middle node in the list because there’s no pointer pointing to it. It is lost in the sea of memory, as good as dead.

5. Search and sort

You can perform binary search in list, but since you need O(n) to get to the middle element, this won’t save time. If you do traverse search, that is O(n).

The same logic applies to sort operations. Normally we will avoid this operation.

6. Example – Sieve of Eratosthenes

 

Notice that unlike the vector version where we just cross-out numbers, in list version we actually delete the numbers. This is a big difference between list and vector operations. You can compare with vector version here.

The result: