Data Structures(1)

Contiguous vs. Linked Data Structures

1.为什么我们要了解常用的数据结构?
Changing the data structure does not change the correctness of the program, since we presumably 
replace a correct implementation with a different correct implementation. 
However, the new implementation of the data type realizes different tradeoffs 
in the time to execute various operations, so the total performance can improve dramatically.

2.学习数据结构的建议
In data structures, as with most subjects, it is more important to really understand
the basic material than have exposure to more advanced concepts. We
will focus on each of the three fundamental abstract data types (containers, dictionaries,
and priority queues) and see how they can be implemented with arrays and lists.

3.Contiguous vs. Linked Data Structures 数组 VS 指针
Data structures can be neatly classified as either contiguous or linked, depending
upon whether they are based on arrays or pointers:
• Contiguously-allocated structures are composed of single slabs of memory, and
include arrays, matrices, heaps, and hash tables.
• Linked data structures are composed of distinct chunks of memory bound
together by pointers, and include lists, trees, and graph adjacency lists.

4.比较
The relative advantages of linked lists over static arrays include:
• Overflow on linked structures can never occur unless the memory is actually full.
• Insertions and deletions are simpler than for contiguous (array) lists.
• With large records, moving pointers is easier and faster than moving the items themselves.
while the relative advantages of arrays include:
• Linked structures require extra space for storing pointer fields.
• Linked lists do not allow efficient random access to items.
• Arrays allow better memory locality and cache performance than random pointer jumping.

5.递归递归!
One final thought about these fundamental structures is that they can be
thought of as recursive objects:
• Lists – Chopping the first element off a linked list leaves a smaller linked list.
This same argument works for strings, since removing characters from string
leaves a string. Lists are recursive objects.
• Arrays – Splitting the first k elements off of an n element array gives two
smaller arrays, of size k and n−k, respectively. Arrays are recursive objects.
This insight leads to simpler list processing, and efficient divide-and-conquer 
algorithms such as quicksort and binary search.