What is a linear list

1, define,

Although the data elements of a linear table are different, the elements in the same linear table must have the same characteristics, that is, belong to the same data object, and there is an order even relationship between adjacent data elements. Such a finite sequence consisting of n (n≥0) elements with the same data properties is called a linear list. When n=0, it is called an empty table.

2, features,

  1. There is a unique data element called “first”
  2. There is a unique data element called “the last”
  3. Except for the first, each data element in the structure has only one precursor
  4. Each data element in the structure has only one successor except the last one

Two, linear table sequential storage representation

The sequential representation of a linear table refers to the sequential storage of the data elements of a linear table by a set of storage cells with contiguous addresses. This representation is also called the sequential storage structure or sequential image of a linear table. A linear table of this storage structure is usually called a Sequential List. It is characterized by the fact that logically adjacent data elements are also physically adjacent. Assume that each element of a linear table occupies len storage cells and the storage address of the first cell is used as the starting storage location of data elements. Then the storage location LOC(AI +1) of the I +1 data element and the storage location LOC(ai) of the I +1 data element in the linear table meet the following relationship:

    LOC(ai+1)=LOC(ai)+len
Copy the code

In general, the storage location of the ith data element AI of a linear table is:

LOC (ai) = LOC (a1) + x len (I - 1)Copy the code

So as long as the starting position of the linear table is determined, any data elements in the linear table can be randomly accessed, so the sequential storage structure of the linear table is a random access storage structure.

JAVA code to implement the sequential storage structure of a linear table

package com.company.struct; /** * @Description SequenceList * @Author stopping * @date: Public class SequenceList<T> {private static final int MAX_SIZE = 100; private static final int MAX_SIZE = 100; /** * list length ** / public int size; /** * private T[] listArray; /** * constructor ** / public SequenceList() {size = 0; listArray = (T[]) new Object[MAX_SIZE]; } /** * add element ** / public int add(T T){int index = size; listArray[size++] = t; return index; } public T get(int I){sure(I); return listArray[i]; } /** * delete element ** / public Boolean remove(int I){/** * 1 2 3 4 5 * ^ * remove index -> 3 2 3 5 ** / sure(I); for (int j = i ; j < size ; j++){ listArray[j] = listArray[j+1]; } subSize(); return true; } private Boolean sure(int I){if (I > MAX_SIZE){throw new RuntimeException(" MAX_SIZE "+MAX_SIZE); } if (I > size){throw new RuntimeException(" subscript exception "); } return true; } /** * private void subSize(){size --; } /** * private void incSize(){size ++; }}Copy the code

Three, linear list chain storage representation

1. Chained linear list

Each element is associated by subsequent Pointers. For example, each element AI and the direct subsequent element AI +1 store the location of AI +1 through the subsequent Pointers of AI. So every piece of data needs to store a successor pointer as well as the data itself. It consists of two domains: the domain storing data element information is called data domain; The domain that stores the immediate successor storage location is called a pointer domain. The information stored in a pointer domain is called a pointer or chain. N nodes (storage image of AI (1≤ I ≤ N)) are linked to form a linked list, that is, a linear list. (a1, a2,… , an) can be distinguished by the number of Pointers, pointer direction and pointer connection mode

  • Singly linked list: has only one pointer field
  • Circular linked list: tail pointer to head pointer
  • Bidirectional linked list: There are two pointer fields
  • Binary list
  • Curb table
  • Adjacency list

Characteristics of 2.

  • The storage unit can be continuous or discontinuous
  • Because each data element points to the next node through a pointer field, it cannot be read randomly.
  • But easy to insert and delete

3. Storage structure example

Single linked list storage structure of a linear list, the access of the entire list must start from the ab initio pointer, the head pointer indicates the storage location of the first node in the list (that is, the storage image of the first data element, also known as the primary node). At the same time, since the last data element has no immediate successor, the pointer to the last node in the singly linked list is NULL.

4. Java code implementation

package com.company.struct; /** * @description LinkList * @author stopping * @date: 2021/6/23 23:17 */ public class LinkList<T> {/** ** private T data; /** * private LinkList next; Public void add(T T){this.next = new LinkList<>(T,next); } public T get(int I){int y = 0; LinkList list = next; // The data field is not empty and the subscript is in range while (list.data! = null && y<i){ list = list.next; y++; } the if (the list data = = null | | y > I) {throw new RuntimeException (subscript crossing the line ""); } return (T) list.data; } public LinkList() { } public LinkList(T data, LinkList next) { this.data = data; this.next = next; } public LinkList(T data) { this.data = data; }}Copy the code