The linear table
define
- Linear tables are the most basic, simplest, and most commonly used data structures. A linear list is a finite sequence of N data elements having the same properties.
- Precursor element: If element A precedes element B, it is called the precursor element of B
- Successor element: If B comes after A, B is said to be A successor element
Characteristics of the
Data elements have a — to — logical relationship.
- The first data element, which has no precursor, is called a header;
- The last data element, which has no successor, is called a tail;
- In addition to the first and last data elements, all data elements have one and only one precursor and one successor.
Classification:
- Data in linear tables can be stored either sequentially or chained
- According to the different storage mode of data, linear list can be divided into sequential list and linked list.
The order sheet
define
A sequential list is a linear list stored in the computer memory in the form of an array. The sequential storage of a linear list means that each element in the linear list is stored in sequence by a set of storage units with contiguous addresses. The data elements that make the linear list ring in the logical structure are stored in adjacent physical storage units. That is, the logical adjacency relation between data elements is reflected by the adjacency relation of physical storage of data elements.
Simple design implementation steps
- Defines an array to store data
- Define an int to record the length of a linear table
- Initialize a linear table with a constructor
- Methods for designing some linear tables
- Private void clear() : Clears a linear table
- Private Boolean isEmpty() : checks whether a linear table isEmpty
- Private int Length () : Gets the number of elements in a linear table
- Private T get(int I) : Reads and returns the value of the ith element in a linear table
- Private void insert(T T, int I) : Insert a value at the position of the ith element in a linear table
- Private void Insert (T T) : Adds elements at the end of a linear table
- Private T remove(int I) : Removes and returns the ith element of the linear table
- Private int indexOf(T T) : returns the first subscript indexOf a specified element in a linear table
- Private void resize(int newSize) : Expansion or reduction of a linear table
package com.study.linear;
public class SequenceList<T> {
// An array of elements
private T[] eles;
// The length of the current linear table
private int N;
// The constructor is initialized
public SequenceList(int capacity) {
this.eles = (T[]) new Object[capacity];
this.N = 0;// The initial linear table has no value and is 0 in length
}
// Clear the linear table
private void clear(a) {
this.N = 0;
}
// Check whether the linear table is empty
private boolean isEmpty(a) {
return this.N == 0;
}
// Get the number of elements in the linear table
private int length(a) {
return this.N;
}
// Reads and returns the value of the ith element in the linear table
private T get(int i) {
T current = eles[i];
return current;
}
// Insert a value at the position of the ith element in the linear table
private void insert(T t, int i) {
// The size of the array is twice that of the original array
if (N==eles.length){
resize(2*eles.length);
}
N++;// Insert, the length of the linear table increases
// move all elements after I back first
for (int j = N - 1; j > i; j--) {
eles[j] = eles[j - 1];
}
// Insert the new value
eles[i] = t;
}
// Add the element at the end of the linear table
private void insert(T t) {
// The size of the array is twice that of the original array
if (N==eles.length){
resize(2*eles.length);
}
eles[N++] = t;
}
// Delete and return the ith element of the linear table
private T remove(int i) {
// Record the deleted element at position I
T remo = eles[i];
// The element after the I position moves forward
for (int j = i; j < N-1; j++) {
eles[j] = eles[j + 1];
}
N--;// delete, the elements of the linear table are reduced
if (N<eles.length/4) {// If it is greater than 1/4, it is reduced by half
resize(eles.length/2);
}
return remo;
}
// Returns the index of the first occurrence of the specified element in a linear table
private int indexOf(T t) {
for (int i = 0; i < N; i++) {
if (eles[i].equals(t)){
returni; }}return -1;/ / not found
}
// Expand and shrink the linear table
// occurs when elements are added and deleted
// Add elements: expand, because the linear table size we defined earlier is fixed
// Delete elements to reduce space waste
private void resize(int newSize){// Resize the linear table according to newSize
// Define a temporary array that points to the original array
T[] temp = eles;
// Create a new array
eles = (T[]) new Object[newSize];
// Pass the value of the temporary array into the new array
for (int i = 0; i < N; i++) { eles[i]=temp[i]; }}public static void main(String[] args) {
SequenceList<String> sl = new SequenceList<>(5);
/ / insert value
sl.insert("Little red");
sl.insert("Little blue");
sl.insert("White");
sl.insert("Little day".1);
System.out.println("The data in the linear table are:");
for (int i = 0; i < sl.length(); i++) {
System.out.println(sl.get(i));
}
System.out.println("The length of the current linear table is:"+sl.length());
/ / delete values
String remove = sl.remove(1);
System.out.println("The element deleted from the linear table is:+remove);
System.out.println("The length of the current linear table is:"+sl.length());
// find a specific value
int index = sl.indexOf("White");
if(index! = -1){
System.out.println("The subscript index of the linear table where White is located is:"+index);
}else {
System.out.println("I can't find white in the linear table.");
}
/ / clear the table
sl.clear();
// Check whether the table is empty
if (sl.isEmpty()){
System.out.println("The linear list has been cleared.");
}else {
System.out.println("Failed to clear the linear table"); }}}Copy the codeThe list
define
A linked list is a non-sequential and non-sequential storage structure on a physical storage unit. Its physical structure cannot only represent the logical order of data elements, but the logical order of data elements is realized through the link order of Pointers in the linked list. A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated at run time.
classification
- Singly linked list
- Two-way linked list
Singly linked list
define
A one-way linked list is a type of linked list. It consists of multiple nodes. Each node consists of a data field for storing data and a pointer field for pointing to its successors. The data field of the head node of the linked list does not store data. The pointer field points to the first node that actually stores data.
Simple design implementation steps
- Define a Node class to implement linked lists
- Define a node to store data
- Define a Node Node to mark the next Node
- No parameter constructor
- Define a head node as the head node
- Defines the length of a linked list of records of type int
- Design some linked list methods
- Private void clear() : Clears the linked list
- Private Boolean isEmpty() : checks whether the list isEmpty
- Private int Length () : Gets the number of elements in the list
- Private T get(int I) : Reads and returns the value of the ith element in the list
- Private void insert(T T, int I) : Insert a value at the position of the ith element in the list
- Private void Insert (T T) : Adds an element to the end of the list
- Private T remove(int I) : Removes and returns the ith element of the list
- Private int indexOf(T T) : returns the indexOf the first occurrence of the specified element in the linked list
- Public void Reserve () : Inverts the entire list
- Public Node reserve(Node Node) : reverses a Node in the list and returns the reversed Node
package com.study.linear;
public class LinkList<T>{
private class Node{
T item;// The data stored in the node
Node next;// Next node
public Node(T item, Node next) {
this.item = item;
this.next = next; }}private Node head;/ / head node
private int N;// Record the length of the list
public LinkList(a){
this.head =new Node(null.null);// Initialize the header
this.N=0;// Initializes the number of linked list elements
}
// Clear the linked list
private void clear(a){
this.head=null;
this.N = 0;
}
// Get the length of the list
private int length(a){
return N;
}
// Check whether the list is empty
private boolean isEmpty(a){
return this.N==0;
}
// Get the element at position I
private T get(int i){
// Loop through the initial node to find the element at position I
Node n = head.next;
for (int j = 0; j < i; j++) {
n = n.next;
}
return n.item;
}
// Add elements to the list
private void insert(T t){
// Find the last node through the loop
Node n = head;
while(n.next! =null){
n = n.next;
}
// Create a new node and place the elements to be added into the new node
Node newNode = new Node(t, null);
// The last node points to the new node
n.next = newNode;
// The length is increased by one
N++;
}
// Add the element at position I
private void insert(T t,int i){
// find the node before position I
Node n = head;
for (int j = 0; j < i; j++) {
n = n.next;
}
// Create a new node, place the elements to be added into the new node, and point to the node at position I
Node newNode = new Node(t, n.next);
// The previous node points to the new node
n.next=newNode;
// The number of elements increases by one
N++;
}
// Remove the element at position I
private T remove(int i){
// find the node before position I
Node n = head;
for (int j = 0; j < i; j++) {
n = n.next;
}// At the end of the loop, n is the previous node of position I
// find the node after position I
Node currentNode = n.next;// Node of position I
Node NextNode = currentNode.next;// The next node of position I
// The node before position I points to the node after position I
n.next=NextNode;
// The number of elements decreases
N--;
return currentNode.item;
}
// Gets the position where the element first appears in the list
private int indexOf(T t){
Node n = head;
for (int i = 0; n.next! =null; i++) {
n = n.next;
if (n.item.equals(t)){
returni; }}return -1;
}
// The entire list is reversed
public void reserve(a){
if (isEmpty()){ // If the list is empty, do not reverse it
return;
}
reserve(head.next);// Call the overloaded method to reverse
}
// a node in the list is reversed, and the reversed node is returned
public Node reserve(Node node){
if (node.next==null){
head.next = node;
return node;
}
// Recursively inverts the next node of the current node, returning the previous node of the current node after the inversion
/ / the original: the head - > 1 - > 2 - > 3
Head ->3->2->1
// If the current node is 1 and the next node is 2, the resulting 2 is the previous node of 1 after the inversion
Node pre = reserve(node.next);
// The current node points to the next node of the returned node
pre.next = node;
// Next node of the current node becomes null
node.next=null;
return node;
}
public static void main(String[] args) {
LinkList<String> il = new LinkList<>();
il.insert("xiao");
il.insert("tai");
il.insert("yang");
il.insert("* * * *".1);
System.out.print("After the addition of elements, the data of the linked list is:");
for (int i = 0; i < il.length(); i++) {
if(i! =il.length()-1){
System.out.print(il.get(i)+",");
}else {
System.out.println(il.get(i));
}
}
il.reserve();
System.out.print("The data after the linked list inversion is:");
for (int i = 0; i < il.length(); i++) {
if(i! =il.length()-1){
System.out.print(il.get(i)+",");
}else {
System.out.println(il.get(i));
}
}
System.out.println("The current length of the list is:"+il.length());
String remove = il.remove(1);
System.out.println("The list deleted elements are:"+remove);
System.out.println("The current length of the list is:"+il.length());
String s = il.get(2);
System.out.println("The data for position 2 is:"+s);
int m = il.indexOf("xiao");
if(m! = -1){
System.out.println("Xiao first appears in the list at:"+m);
}else {
System.out.println("Xiao does not appear in the linked list ~"); }}}Copy the codeTwo-way linked list
define
A bidirectional linked list, also known as a bidirectional list, is a type of linked list. It is composed of multiple nodes, each node is composed of a data field and two pointer fields. The data field is used to store data, and one pointer field is used to point to the successor node and the other pointer field is used to point to the precursor node. The data field of the head node of the linked list does not store data, the field value of the pointer to the precursor node is null, and the field value of the pointer to the successor node points to the first node that actually stores data.
Simple design implementation steps
- Create a Node class to implement the linked list
- Create a data domain to store data
- Create the precursor, Pre
- Create the successor last
- Create a parameterized construct
- Create the head header
- Create the last tail
- Create an integer N of type int to record the length of the list
- Design some linked list methods
- Private void clear() : Clears the linked list
- Private Boolean isEmpty() : checks whether the list isEmpty
- Private int Length () : Gets the number of elements in the list
- Private T get(int I) : Reads and returns the value of the ith element in the list
- Private void insert(T T, int I) : Insert a value at the position of the ith element in the list
- Private void Insert (T T) : Adds an element to the end of the list
- Private T remove(int I) : Removes and returns the ith element of the list
- Private int indexOf(T T) : returns the indexOf the first occurrence of the specified element in the linked list
- Public T getFirst() : Gets the first element
- Public T getLast() : Gets the last element
package com.study.linear;
public class TwoWayList<T> {
private Node head;/ / head node
private Node last;/ / end nodes
private int N;// List length
/ / node class
private class Node{
private T item;
private Node pre;
private Node next;
public Node(T item, Node pre, Node next) {
this.item = item;
this.pre = pre;
this.next = next; }}// Initialize the linked list
public TwoWayList(a){
// Initialize the header
this.head=new Node(null.null.null);
// Initialize the end node
this.last=null;
// Initialize the number of elements
this.N=0;
}
// Clear the linked list
public void clear(a){
this.head.next=null;
this.last=null;
this.N=0;
}
// Check whether the list is empty
public boolean isEmpty(a){
return this.N==0;
}
// Get the number of elements in the list
public int length(a){
return N;
}
// Gets and returns the value of the ith element in the list
public T get(int i){
// Get the node of element i-1
Node n = head;
for (int j = 0; j < i; j++) {
n = n.next;
}
return n.next.item;
}
// Add values to the list
public void insert(T t){
Node n = head;
if (isEmpty()){// The linked list is empty
// Create a new node
Node newNode = new Node(t,head,null);
// The new node becomes the end node
last = newNode;
// The header points to the tail
head.next = last;
}else { // The linked list is not empty
// Create a new node
Node newNode = new Node(t,last,null);
// The current endpoint points to the new endpoint
last.next = newNode;
// make the new node the final node
last = newNode;
}
// The number of elements is +1
N++;
}
// Add the value at position I
public void insert(T t,int i){
Node n = head;
// the node at position i-1
for (int j = 0; j < i; j++) {
n = n.next;
}
// node of position I
Node currentNode = n.next;
// Create new node
Node newNode = new Node(t,n,currentNode);
// the end of i-1 points to the new node
n.next = newNode;
// the header of I points to the new node
currentNode.pre = newNode;
// The number of elements is increased by one
N++;
}
// Delete and return the value of the ith position in the list
public T remove(int i){
Node n = head;
for (int j = 0; j < i; j++) {
n = n.next;
}
// the node of position I
Node currentNode = n.next;
// I +1 node
Node nextNode = currentNode.next;
// the node of i-1 points to the node of I +1
n.next = nextNode;
nextNode.pre = currentNode;
// Delete the element, the number of elements is reduced by one
N--;
return currentNode.item;
}
// Returns the subscript index of the element at the specified position in the list
public int indexOf(T t){
Node n = head.next;
for (int i = 0; n.next! =null; i++) {
if (n.item.equals(t)){
return i;
}
n = n.next;
}
return -1;
}
// Get the first element
public T getFirst(a){
return head.next.item;
}
// Get the last element
public T getLast(a){
return last.item;
}
public static void main(String[] args) {
TwoWayList<String> il = new TwoWayList<>();
il.insert("xiao");
il.insert("tai");
il.insert("yang");
il.insert("* * * *".1);
System.out.print("After the addition of elements, the data of the linked list is:");
for (int i = 0; i < il.length(); i++) {
if(i! =il.length()-1){
System.out.print(il.get(i)+",");
}else {
System.out.println(il.get(i));
}
}
System.out.println("The current length of the list is:"+il.length());
System.out.println("The first element in the current list is:"+il.getFirst());
System.out.println("The last element in the current list is:"+il.getLast());
String remove = il.remove(1);
System.out.println("The list deleted elements are:"+remove);
System.out.println("The current length of the list is:"+il.length());
String s = il.get(2);
System.out.println("The data for position 2 is:"+s);
int m = il.indexOf("tai");
if(m! = -1){
System.out.println("Tai first appears in the list at:"+m);
}else {
System.out.println("Tai does not appear in the linked list."); }}}Copy the codeArrayList, and LinkedList
ArrayList
- Implement with arrays
- The array has been expanded
- Provides a traversal mode
View the source code and analyze the Add method
LinkedList
- Use a bidirectional linked list
- The node class has three pointer fields
View the source code and analyze the Add method
Sequential lists vs linked lists
- Sequential table data is fast to be queried but slow to be added or deleted
- Linked lists add and delete data fast, slow query data (query intermediate value, the introduction of the fast and slow pointer query, faster)
- Sequential lists are implemented in arrays with contiguous physical addresses
- Linked lists are implemented with pointer fields, and the physical addresses are random and irregular
- Sequential tables open arrays of fixed size at once. In addition to dynamically changing the size of the array, otherwise space may be wasted or the array is not enough, and some data cannot be stored
- Linked list is dynamic open up space, when the need to open up, will not produce space waste
Blog references for other knowledge points
- A fast or slow pointer to a linked list
- The fast and slow pointer to the linked list and determine whether the linked list has a ring
- If there are rings, find the entrance and length of the rings
- Cyclic linked lists and Joseph’s problem