preface

Data structure is the basic skill of programmer. Program = data structure + algorithm. This chapter is my own learning record

1, Introduction to data structure

   Different data structures have their own usage scenarios,
The purpose is to reduce the time complexity and space complexity. Generally, space is used for time,
Speed up the program.

2, Data structure division

   1. Data storage: the bottom layer of data storage is through the <array> and <Linked list> To store
   2. Data structure division: according to the physical logic, it can be divided into <linear structure> as well as <Nonlinear structure>
a)The linear structure is as follows「array」,「Linked list」,「Stack」,「queue」,
b)The nonlinear structures are as follows「tree」,「chart」,「Dictionaries」,「heap」. 

The rookie PS is a graph that uses the data structure of graphic algorithm. This book is excellent. It is learned by WeChat official account "programmer skin". If there is any infringement message, I delete the picture. It is not used for business, but for interest study. Most of the plans used later are from other places, but do not like to spray.

This section will use the initialization and construction methods of each data structure in C # language to introduce the basic characteristics of each data structure.

1. array:
   Array is a collection of elements of the same type, which is stored in a continuous memory space of the computer and accessed by subscript.
   a) Search is to calculate the offset to find other values, so the time complexity is O(1)
   b) The operations of adding, deleting and modifying will move the original elements, so the time complexity is: O(n)

// Initialize an array of length 5
int[] array = new int[5];
// Element assignment 
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
// Initialization method of direct assignment
int[] array = {2, 3, 1, 0, 2};

"List array" is a frequently used data structure, which is more flexible than ordinary array. Common operations are: access elements, add elements, delete elements.

// C # initialize variable array List
List<int> array = new List<int>();

// Add element to tail
array.Add(2);
array.Add(3);
array.Add(1);
array.Add(0);
array.Add(2);

1. List ListNode:
   The linked list is stored in a discontinuous memory space of the computer. ListNode is the node object, val is the value of the storage data element, and next is the pointer to store the address of the next node.

// Define a linked list
public class ListNode {
     public int val;
     public ListNode next;     
     public ListNode(int val=0,ListNode next=null) 
     {
         this.val = val;
         this.next = next;
     }
 }

1. stack:
   Stack is sequential, in a continuous memory, the feature is "first in, last out", which is automatically allocated and maintained by the system, and can be realized through array or linked list.

// Initialize a stack
Stack st = new Stack();

// Define a stack through an array
public class CustomStack {
    int[] stack;
    int top;
    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        top =-1;
    }
    public void Push(int x) {
        if(top!=stack.Length-1)
        {
            top++;
            stack[top]=x;
        }
    }
    public int Pop() {
        if(top==-1)
        {
            return -1;
        }
        --top;
        return stack[top + 1];
    }
}

The common operations push(), pop(), show the characteristics of the stack.

// Initialize a stack
st.Push('1');  //Stack element 1
st.Push('2');  //Stack element 2
st.pop();      //Element 2 out of stack 
st.pop();      //Element 1 out of stack

1. queue:
   Queue is also sequential, the feature is the first in the last out, can use arrays and linked lists.

// Initialize a queue
Queue q = new Queue();

The common operations "queue push()," queue pop() "show the first in first out feature of the stack.

q.Enqueue(1);  //Stack element 1
q.Enqueue(2);  //Stack element 2
q.Dequeue();  //Element 1 out of the team  
q.Dequeue();  //Element 2 out of the team

1. TreeNode:
   Tree definition: full binary tree, complete binary tree, search binary tree, balanced search binary tree
   Tree storage: array and linked list storage, generally recommended linked list
   Tree traversal: depth first DFS and breadth first BFS
   Depth first includes preorder traversal
   Two traversal methods: recursion and iteration
   ListNode is the node object, val is the value of the storage data element, left is the left pointer of the storage data element, and right is the right pointer of the storage data element.

// Define a tree
public class TreeNode {
      public int val;
      public TreeNode left;
      public TreeNode right;
      public TreeNode(int val=0, TreeNode left=null, 
      TreeNode right=null) 
      {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

// Initialize node
TreeNode n1 = new TreeNode(3); // Root node root
TreeNode n2 = new TreeNode(4);
TreeNode n3 = new TreeNode(5);
TreeNode n4 = new TreeNode(1);
TreeNode n5 = new TreeNode(2);

// Building reference points
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

1. Dictionary:
   Dictionary and hashtable are a set of Key Value pairs,
   choice:
   a) The integer speed of dictionary is better than hash table
   b) The dictionary does not need to be boxed, and its speed is better than hash table
   c) Multithread dictionary non thread safe lock judgment will affect the speed

// Initialize a Dictionary

var myDictionary=new Dictionary<int,string>();

// add to
myDictionary.Add(1,"C#");
myDictionary.Add(2,"JAVA");
myDictionary.Add(3,"C");

// visit
myDictionary[1]  //C#

summary

This paper only briefly introduces the declaration definition and use of basic data types, while common data types provide a large number of functions and methods that can make us deal with data quickly and conveniently.