# 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.

- 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);

- 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; } }

- 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

- 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

- 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;

- 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#