What is a linear table?

Catalog

The linear table （List）

1. The order sheet （ArrayList）

2. Linked list （LinkedList）

---

The linear table （List）

Between elements is a “ linear ” The relationship between , Each element has at most one precursor and successor .

Linear table can be divided into sequence table and chain table .

1. The order sheet （ArrayList）

① Sequence table is a broader concept in data structure , An array is Java More specific concepts in , Arrays are a typical way to implement sequential tables ;

② Between elements , In contiguous memory space （ In order , But it doesn't mean order ）;

③capacity Containers 、size Element number , All subscripts in the linear table are only related to the number of elements , Container independent ;

④Java When implementing the sequence table , There is a special class ArrayList（ Generic classes , Specify through generic parameters ArrayList What types of data can be stored in ）, It encapsulates ordinary arrays ;

⑤ArrayList It's the realization of List The class of the interface , That is the List Abstract methods in （ Common methods of adding, deleting, modifying and checking ） Duyi Once realized .

---

2. Linked list （LinkedList）

The linked list contains many nodes （ Of course, it can also contain zero nodes ）. Every node （Node） It contains the value of the element （value） And point to （next）,next Used to point to the next node , The tail node points to null.

public class Node {
  
      int value; // value   
      Node next; // Point to 
       
  }

① Between elements , Can be in discontinuous memory space ;

② Linked lists have nothing to do with arrays , Can't use index Direct subscript removal , But it can be done get/set Method to get the subscript , It's just more inefficient than sequential subscript removal ;

③ A linked list is different from a sequential list , Sequential tables are in contiguous memory space , As long as you continue down the memory, you can find the next node （ Subscript self increasing ）; The linked list finds nodes through nodes ;

④ In a one-way list ： Only through the current node , Find the next node , Cannot find the previous node , For a single chain watch , As long as you know the head node of the linked list , You can get all the elements of the linked list , You can use the head node to refer to the entire linked list , For example, parameters in methods ;

  In a two-way list ： Through the current node , You can find the next node , You can also find the previous node ;

⑤ Linked list with puppet nodes ： Not actually storing data , Just for a place ;

    Linked list without puppet nodes ： Actual stored data ;

⑥ Linked list ： The last element does not point to null, Instead, it points to a node on the linked list ;

    Linked list without Links ： The last element points to null;

④⑤⑥ These three sets of attributes are irrelevant , You can rehearse the combination at will , Derived from 8 Middle linked list ！

（ One way without puppets and rings and Two way puppet belt ring These two kinds are more common ）

In essence, it is to solve the problem of “ Carry ” problem , For example, insert or delete in the middle , Can directly change next The direction of , Linked list is avoided “ Carry ”;