1, an overview of the

Data Structure: It is an independent discipline of computer major, mainly studying the logical structure and storage structure of data and the relationship between data

Logical structure: mainly use 4 — set, linear structure, tree (elements are built between the hierarchical relationship), graph (mesh relationship)

** Collection: ** A container for data (Chapter 3 research)

** Linear structure: ** Each element except the first element has only one precursor, and each element except the last element has only one afterdrive;

Linear table, stack (features: advanced back out), queue

Storage structure: How data is stored on a disk;

Sequential storage (storing data in contiguous space on disk);

Chain storage (data stored anywhere on disk), unidirectional chain storage (single linked list), bidirectional chain storage (double linked list), circular chain storage (circular linked list)

2. Linear tables

Implement linear structures based on arrays (use arrays to store data and keep a linear relationship between elements)

Write linear structured data structures

public void insert(int i,Object data); // Add to the position specified in the linear table; public void append(Object data) ; // Append to the end of the linear table; public void remove(int i); public void update(int i,Object data); // I is the subscript; public Object get(int i); public Object[] list(); public int size(); // The number of linear table elements; public boolean isEmpty(); // Whether the linear table is empty;Copy the code

Summary: Common operations on data: retrieve, insert, delete, update, sort

3, stack (stack)

SUN has implemented the design in the JDK – the java.util.stack class

public void push(Object data);
public Object pop();
public Object seek();
public int size();
public boolean isEmpty();
Copy the code
4. Queue

Queue features: First in, first out (FIFO)

The LinkedList class is an implementation of the Queue interface, which SUN implemented in the JDK

boolean offer(E e); // Add data to the queue Object poll(); // Delete the queue Object peek(); // return the first element in the queue (not deleted) int size(); boolean isEmpty();Copy the code
5, the algorithm

Search: traversal, binary search (for a sorted sequence)

Sort: 4 sort algorithms (bubble sort, select sort, insert sort, quicksort)