Linear table_ list
definition
A linear table is an ordered sequence of N data elements. A data element can be composed of several data items. Data elements can be called records. A large number of records are called files.
Characteristics of linear structure
In a non empty finite set of data elements,
- There is a unique data element called "first";
- There is a unique data element called "last";
- Except for the first, each data element in the set has only one precursor;
- Except for the last one, each data element in the collection has only one afterdrive.
Representation of linear table
Sequential representation
It refers to the use of a set of storage units with continuous addresses to store the data elements of the linear table in turn. Logically adjacent addresses must be physically adjacent.
The storage location of the first data element of a linear table is called the starting location or base address. As long as the starting position is determined, any data element in the linear table is random access. Therefore, the sequential storage structure of the linear table is a random access storage structure.
The three elements of the sequence table: the first address of the space; Space size; Number of elements (storage capacity at that time).
Because inserting and deleting data elements will lead to the movement of data elements in the sequence table, the sequence table has the disadvantage that the change of data elements is particularly time-consuming.
Chain representation
It refers to using a set of arbitrary storage units to store the data elements of a linear table. Logically adjacent addresses are not necessarily physically adjacent.
Each data element has a data part and a correction part. The part storing the information of the data element is called the data field, and the part storing the subsequent location information is called the pointer field. The information stored in the pointer is called a pointer or chain. Such a data element is called a Node, and multiple nodes are linked into a linked list.
The first node of the linked list is called the head node.
When inserting and deleting elements in the linked list, you don't need to move the data elements, you just need to modify the pointer in the node.
Single linked list
The link direction of one-way linked list (single linked list) is one-way, and the access should be read sequentially from the head.
The node of a one-way linked list is divided into two parts: 1 is the data area, which is used to save data, and 2 is the pointer area, which is used to store the address of the next node., The pointer to the last node is null.
package linkedList;
/**
* Single linked list
*/
public class SingleLinkedList {
/**
* Number of nodes
*/
private int length;
/**
* Head node
*/
private Node head;
public SingleLinkedList() {
length = 0;
head = null;
}
private class Node {
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
}
public Object addHead(Object object) {
Node newNode = new Node(object);
if (length == 0) {
head = newNode;
} else {
head = newNode;
newNode.next = head;
}
length++;
return object;
}
public boolean delete(Object value) {
if (length == 0) {
return false;
}
Node current = head;
Node previous = head;
while (current.data != value) {
if (current.next == null) {
return false;
} else {
previous = current;
current = current.next;
}
}
if (current == head) {
head = current.next;
length--;
} else {
previous.next = current.next;
length--;
}
return true;
}
public Node find(Object object) {
Node current = head;
int tempSize = length;
while (tempSize > 0) {
if (object.equals(current.data)) {
return current;
} else {
current = current.next;
}
tempSize--;
}
return null;
}
}
Bidirectional linked list
The pointer field of each node of the two-way linked list has two pointers, pointing to its direct successor and direct predecessor nodes respectively. In this way, we can access and process node data from two directions.
package linkedList;
/**
* Bidirectional linked list
*/
public class TwoWayLinkedList {
/**
* Number of nodes
*/
private int length;
/**
* Head node
*/
private Node head;
/**
* Tail node
*/
private Node tail;
private class Node {
private Object data;
private Node next;
private Node prev;
public Node(Object data) {
this.data = data;
}
}
public TwoWayLinkedList() {
length = 0;
head = null;
tail = null;
}
/**
* Add nodes to the head of the linked list
*
* @param value
*/
public void addHead(Object value) {
Node newNode = new Node(value);
if (length == 0) {
head = newNode;
tail = newNode;
length++;
} else {
head.prev = newNode;
newNode.next = head;
head = newNode;
length++;
}
}
/**
* Add nodes at the end of the linked list
*
* @param value
*/
public void addTail(Object value) {
Node newNode = new Node(value);
if (length == 0) {
head = newNode;
tail = newNode;
length++;
} else {
newNode.next = tail;
tail.next = newNode;
tail = newNode;
length++;
}
}
/**
* Delete header node
*
* @return
*/
public Node deleteHead() {
Node temp = head;
if (length != 0) {
head = head.next;
head.prev = null;
length--;
return temp;
} else {
return null;
}
}
/**
* Delete tail node
*
* @return
*/
public Node deleteTail() {
Node temp = tail;
if (length != 0) {
tail = tail.prev;
tail.next = null;
length--;
return temp;
} else {
return null;
}
}
}
Circular linked list
The pointer field of the last node in the table points to the head node, and the whole linked list forms a ring. Unidirectional.
Static linked list
An array is used to represent the linked list. The data element in the data is a node element. The node element contains data members and array subscript members. The chain is formed by storing the array subscript of the next node.
Comparison between chain representation and sequential representation
Advantages and disadvantages of chain
The rational use of storage space, as long as it is not a physically continuous storage unit.
There is no need to move elements when inserting and deleting data elements, which is fast
Random access is not available and the speed is slow
Advantages and disadvantages of sequential
Storage space must be and continuous
Inserting and deleting data elements requires moving elements, which is slow
Random storage can be carried out, and the search speed is fast
reference resources
Data structure (C language version) Yan Weimin
Core knowledge points of Java interview Wang Lei