A stack,
After the advanced
Second, the queue
First in first out
Three, arrays,
Fast query: only need to correspond to the array address, element address continuously add and delete slow: need to create a new array, the source array destruction
Fourth, the linked list
Slow query: address discontinuous, each query elements need to be queried from the beginning to add or delete fast: Each element in a list is also called a node. A node in a one-way list contains a data source (storing data) and two pointer fields (current address and next element address). A node in a two-way list has one more pointer field (previous element address) than a node in a one-way list.
1. Features of one-way linked list
List order cannot be guaranteed: the order in which elements are stored and retrieved may not be the same
2. Bidirectional linked list features
It is an ordered collection because there is an extra pointer to the previous element
3. The analysis
A. the list interface and list inequitable b. list interface set of commonly used three kinds of implementation class ArrayList, respectively, LinkedList, the Vector c. ArrayList, although the Vector has realized the list interface, However, d. LinkedList based on array data structure also realizes list interface, but based on bidirectional LinkedList data structure, bidirectional LinkedList data structure also needs to write code to achieve later.