I Data structure overview
Data Structure is a subject that studies the organization and management of data. It is often expressed externally as a collection or container of a set of data.
Concept explanation:
Element: managed atomic data, unlimited element types.
Collection: a container for storing elements. It needs to organize elements with certain data structure knowledge.
Traversal / Iterate: in the context of data structure, it often means that all elements in a set are processed once in a certain order.
Data logical structure: refers to the data structure that reflects the logical relationship between data elements. The logical structure refers to the front and back relationship between data elements, regardless of their storage location in the computer.
The logical structure includes:
Set: there is no other relationship between the elements in the data structure except the mutual relationship of "belonging to the same set";
Linear structure: there is a one-to-one relationship between the elements in the data structure;
Tree structure: there is a one to many relationship between the elements in the data structure;
Graphic structure: there is a many to many relationship between the elements in the data structure.
Data storage structure: the storage form of the logical structure of data in the computer storage space is called the physical structure of data (also known as storage structure). Generally speaking, the logical structure of a data structure can be expressed into a variety of storage structures according to needs. The commonly used storage structures include sequential storage, chain storage, index storage and hash storage.
The characteristics of the sequential storage structure of data are: using the relative position of elements in the memory to represent the logical relationship between data elements; The characteristic of non sequential storage is that the logical relationship between data elements is represented by the pointer indicating the storage address of elements.
II Linear table - sequence table
A linear list is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables: sequential table, linked list, stack, queue, string
A linear table is logically a linear structure, that is, a continuous straight line. However, the physical structure is not necessarily continuous. When the linear table is stored physically, it is usually stored in the form of array and chain structure.
List and ArrayList in Java
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;
/**
* linear structure
* characteristic:
* 1. There is a contextual relationship between elements
* 2. The element will have the concept of the first position. The position is represented by an index, starting from 0
* 3. Insertion can be divided into head insertion, tail insertion and insertion by position according to different positions
* 4. Deletion can be divided into header deletion, tail deletion and deletion by location according to different locations
* 5. Traversal can be divided into forward traversal and backward traversal
* 6. Java In, List is an interface and a sub interface of Collection
*/
public interface List extends Collection {
/**
* Insert the e-tail into the linear table
* @Parameter e element to be inserted
* @The return value must be true, indicating successful insertion. Linear tables will not be inserted unsuccessfully
*/
boolean add(Element type e);
/**
* Insert e into the index position of the linear table; The original index and subsequent elements are required to move backward
* index The optional range of is 0 < = index < = size ()
* @Parameter index insertion position (subscript)
* @Parameter the element to be inserted
*/
void add(int index, Element type e);
/**
* Delete the element at the index position and return the element; The original index + 1 and subsequent elements are required to move forward
move
* index The optional range of is 0 < = index < size ()
* @Parameter index position to be deleted (subscript)
* @Returns the element whose value has been deleted
*/
Element type remove(int index);
/**
* Delete the first equal element encountered when traversing from front to back
* @Parameter element to be deleted
* @Return value true: deletion succeeded; false: no equivalent element found
*/
boolean remove(Element type e);
/**
* Returns the element at the index position
* index The optional range of is 0 < = index < size ()
* @Parameter index gets the position (subscript) of the element
* @Returns the element obtained by the value
*/
Element type get(int index);
/**
* Replace the element at the index position with the new element e and return the original element at the index position
* index The optional range of is 0 < = index < size ()
* @Parameter index the position of the element to be replaced (subscript)
* @Parameter e new element to replace
* @Returns the old element at the index position of the value
*/
Element type set(int index, Element type e);
/**
* Through traversal, judge whether the element equal to element e exists in the linear table
* @Parameter e element to be found
* @Return true: include; false: does not contain
*/
boolean contains(Element type e);
/**
* Find the subscript of the first element equal to element e by traversing from front to back
* @param e Element to be found
* @return >= 0 Indicates that the subscript is found and returned- 1 means not found
*/
int indexOf(Element type e);
/**
* Find the subscript of the first element equal to element e by traversing from back to front
* @param e Element to be found
* @return >= 0 Indicates that the subscript is found and returned- 1 means not found
*/
int lastIndexOf(Element type e);
/**
* Clear the linear table, that is, after calling clear(), the size() = 0 of the linear table; isEmpty() ==
true
*/
void clear();
/**
* Returns the number of existing elements in a linear table
* @return Returns the number of elements
*/
int size();
/**
* Returns whether the linear table is an empty container
* @return true Empty container
*/
boolean isEmpty();
import java.util.*;
public abstract class MyArrayList<E> implements List<E> {
private E[] array;
private int size;
public MyArrayList(){
array = (E[])new Object[16];
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
if(o == null){
//Cannot use equals to judge
for(int i = 0;i < size; i++){
if(array[i] == o){
return true;
}
}
return false;
} else {
for(int i = 0;i < size;i++){
if(o.equals(array[i])){
return true;
}
}
return false;
}
}
@Override
public Iterator<E> iterator() {
return null;
}
@Override
public Object[] toArray() {
return new Object[0];
}
@Override
public <T> T[] toArray(T[] a) {
return null;
}
@Override
public boolean add(E e) {
ensuerCapacity();
array[size++] = e;
return true;
}
private void ensuerCapacity() {
if(size < array.length){
return;
}
array = (E[]) Arrays.copyOf(array,array.length*2);
}
@Override
public boolean remove(Object o) {
if(o == null){
for(int i = 0;i < size;i++){
if(array[i] == o){
System.arraycopy(array,i + 1,array,i,size - i - 1);
array[--size] = null;
return true;
}
}
return false;
} else {
for(int i = 0;i < size;i++){
if(o.equals(array[i])){
System.arraycopy(array,i + 1,array,i,size - i - 1);
array[--size] = null;
return true;
}
}
return false;
}
}
@Override
public boolean addAll(Collection<? extends E> c) {
for(E e : c){
add(e);
}
return true;
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
for(E e : c){
add(index,e);
}
return true;
}
@Override
public void clear() {
Arrays.fill(array,null);
size = 0;
}
@Override
public E get(int index) {
if(index < 0 || index < size){
throw new ArithmeticException(String.format("index = %d,size = %d",index,size));
}
return array[index];
}
@Override
public E set(int index, E element) {
if(index < 0 || index <= size){
throw new ArithmeticException(String.format("index = %d,size = %d",index,size));
}
E oldValue = array[index];
array[index] = element;
return oldValue;
}
@Override
public void add(int index, E element) {
if(index < 0 || index > size){
throw new ArithmeticException(String.format("index = %d,size = %d",index,size));
}
ensuerCapacity();
System.arraycopy(array,index,array,index + 1,size - index);
}
}III Linear list linked list
Element: the content that really exists in the linear table is the core content we care about.
Node: a structure introduced to organize the linked list. It not only saves our elements, but also saves the reference to the next node
Current / cur: indicates a node in the linked list.
Previous / prev: indicates the previous node of a node in the linked list; The head node has no precursor node.
Next: indicates the next node of a node in the linked list; The tail node has no successor node.
Definition and creation of linked list
public class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
@Override
public String toString() {
return "Node{" + val + "}";
}
}
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n5 = new Node(5);
n1.next = n2;
n2.next = n5;
n5.next = null;
Node head = n1;
Traversal of linked list
Node cur = head;
while (cur != null) {
cur = cur.next;
}Element insertion and deletion of linked list
Header deletion
public static void main(String args) {
Node head = build();
head = pushFront(head, 0);
// Verify whether the head is inserted correctly by traversing the print
}
private static Node pushFront(Node head, int v) {
Node node = new Node(v);
node.next = head;
head = node;
return head;
}
Head insert
public static void main(String args) {
Node head = build(); // The following situations need to be considered: the linked list is empty; There are elements in the linked list
head = popFront(head);
// Verify whether the header deletion is correct by traversing the print
}
private static Node popFront(Node head) {
if (head == null) {
throw new RuntimeException("The linked list is empty");
}
head = head.next;
return head;
}
Tail deletion
public static void main(String args) {
Node head = build(); // The following situations need to be considered: the linked list is empty; There are elements in the linked list
head = pushBack(head, 0);
// Verify whether the tail insertion is correct by traversing the print
}
private static Node pushBack(Node head, int v) {
if (head == null) {
Node node = new Node(v);
return node;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
Node node = new Node(v);
last.next = node;
return head;
}Tail insertion
public static void main(String args) {
Node head = build(); // The following situations need to be considered: the linked list is empty; There is an element in the linked list; In the linked list
Multiple elements
head = popFront(head);
// Traverse the print head and verify whether the deletion is correct
}
private static Node popBack(Node head) {
if (head == null) {
throw new RuntimeException("The linked list is empty");
}
if (head.next == null) {
head.next = null;
return head;
}
Node last2 = head;
while (last2.next.next != null) {
last2 = last2.next;
}
last2.next = null;
return head;
}