“This is the 13th day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021”.
The implementation logic of array and linked list based on Java linear list is introduced in detail, and the Java implementation cases of array linear list, single linked list and static linked list are attached.
Linear list: a finite sequence of zero or more data elements. Linear tables include arrays, linked lists, stack Spaces, queues and other structures.
The most basic linear table is described as follows: The set of data objects in a linear table is {A1, A2,…… ,an}, except for the last element,an, each element has and only one immediate successor element data, and the relationship between elements is one-to-one. As data structures evolved, more complex linear tables followed, which may have other properties but adhere to the basic properties above.
The linear table above refers to a logical data structure, and for the realization of this logical structure, namely physical structure, using sequential storage structure and linear storage structure can be realized. For a primer on sequential and linear storage structures and data structures, see this blog post:Introduction to data structure and classification.
The sequential storage structure of linear tables
1.1 Overview of linear table sequential storage architecture
The sequential storage structure of a linear table refers to the sequential storage of the data elements of a linear table with contiguous addresses.
Linear tables (A1, A2,…… ,an) is stored in sequence as follows:
We can use arrays to implement the sequential storage structure of linear tables. The first data element is stored at a position with subscript 0 in the array, called an index, and the contiguous elements of the linear table are stored at contiguous positions in the array.
The length of an array is the size of the storage space used to store a linear table, which is generally constant after storage allocation. Extending generally means creating a larger array and copying the elements of the original array into the new array.
The length of a linear table is the number of data elements in a linear table, which varies with insertion and deletion operations.
Storing sequential tables in arrays means allocating fixed-length array space, which is greater than or equal to the length of the current linear table because insertion and deletion can be performed in a linear table.
1.2 Search for the sequential storage structure of linear tables
Each location in memory has its own number, called an address. Since the storage cells of an array are contiguous and each element has the same amount of space, we can calculate the address of any position in a linear table at any time, regardless of whether it is the first or the last, at the same time.
So the data we put in or take out of each linear table location is equal time to the computer, which is a constant, so using the concept of time complexity that we learned in our algorithm, its access time is O(1). We usually refer to the storage structure with this characteristic as random access structure.
1.3 Adding and deleting linear table sequential storage structure
Array-based linear table lookups are fast, but slow if you want to add or remove data anywhere.
- Add new data to index I in array:
- First determine if the insertion position is not reasonable, throw an exception;
- If the length of the linear table is greater than or equal to the length of the array after insertion, an exception is thrown or the capacity is dynamically increased.
- Iterate over all the elements following the index I, moving them back one place each;
- Insert the element into index I and increase the table length by 1.
- Delete new data from array at index I:
- If the deletion location is inappropriate, throw an exception.
- Remove the deleted element;
- Iterate over all the elements following the index I, moving them all forward one place each;
- Set the value of the last element to NULL;
- The table length is reduced by 1.
As can be seen from the above steps, the data after the target position must be moved forward or backward, with the number of elements n.
In the best case, if you want to insert the element to the last position, or delete the last element, the time is O(1), because you don’t need to move the element.
In the worst case, if you add or remove elements in the array header, that means moving all elements backwards or forwards, so the time is O(n).
In the average case, the final average number of moves is the same as the number of moves of the element in the middle of the operation, which is n minus 1 over 2.
Therefore, the time complexity of adding and deleting elements in an array is O(n).
1.4 Advantages and disadvantages of linear table sequential storage structure
1.5 simple implementation of linear table sequential storage structure
/** * a simple array implementation of the sequential storage structure of a linear table, designed to be unextensible for demonstration purposes. * /
public class MyFinalArrayList<E> {
/** * The bottom layer uses arrays to store data */
private final Object[] elements;
/** * The number of elements currently stored */
private int size;
/** * Total capacity, array length */
private final int capcity;
/** * initializes array ** in the constructor@param capcity
*/
public MyFinalArrayList(int capcity) {
this.capcity = capcity;
elements = new Object[capcity];
}
/** * add a new element to the table **@paramElement The added element *@returnReturn true on success, false */ on failure
public boolean add(E element) {
// Whether the capacity of the linear table is full
if (size == capcity) {
// Add failed to return false
return false;
}
// Add an element to the size index, and size increases by 1
elements[size++] = element;
// Return true, adding succeeded
return true;
}
/** * deletes an element. By default, the first ** of the linear table is deleted@returnReturns the deleted element or null */
public E delete(a) {
// If the list is empty, return empty
if (size == 0) {
return null;
}
// The number of elements to move
int length = size - 1;
// The element to be deleted
Object e = elements[0];
// Move all subsequent elements
System.arraycopy(elements, 1, elements, 0, length);
// The last element is left empty
elements[--size] = null;
return (E) e;
}
/** * removes the first element that is the same as the input element */
public boolean delete(Object element) {
if (size > 0) {
for (int index = 0; index < size; index++) {
if (element == null) {
if (elements[index] == null) {
int numMoved = size - index - 1;
System.arraycopy(elements, index + 1, elements, index, numMoved);
elements[--size] = null;
return true; }}else {
if (element.equals(elements[index])) {
int numMoved = size - index - 1;
System.arraycopy(elements, index + 1, elements, index, numMoved);
elements[--size] = null;
return true; }}}}return false;
}
/** * deletes the element at an index */
public E delete(int index) {
rangeCheck(index);
E e = (E) elements[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elements, index + 1, elements, index, numMoved);
}
elements[--size] = null;
return e;
}
/** * Updates the element value of an index */
public void set(int index, Object newElement) {
rangeCheck(index);
elements[index] = newElement;
}
/** * contains an element **@param* element element@returnFalse does not contain true contains */
public boolean contains(Object element) {
if (size > 0) {
for (int index = 0; index < size; index++) {
if (element == null) {
if (elements[index] == null) {
return true; }}else {
if (element.equals(elements[index])) {
return true; }}}}return false;
}
/** * gets the element ** of the specified index@paramIndex Specifies the index *@returnSpecifies the index element */
public E get(int index) {
// Check index out of bounds
rangeCheck(index);
return (E) elements[index];
}
/** * returns the first element **@returnThe first element, or null has no element */
public E get(a) {
if (size > 0) {
return (E) elements[0];
}
return null;
}
/** * returns the index of the first occurrence of the specified element **@paramElement specifies the element *@returnReturn index, or -1, the element */ was not found
public int indexOf(Object element) {
if (size > 0) {
for (int index = 0; index < size; index++) {
if (element == null) {
if (elements[index] == null) {
returnindex; }}else {
// By default, equals is used to compare elements for equality
if (element.equals(elements[index])) {
returnindex; }}}}// No element found, return -1
return -1;
}
/** * returns the number of linear table elements **@returnNumber of linear table elements */
public int size(a) {
return size;
}
/** * overrides toString method **@return* /
@Override
public String toString(a) {
if (size == 0) {
return "[]";
}
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(elements[i]);
if(i ! = size -1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
/** * check index */
private void rangeCheck(int index) {
if (index >= size) {
//throw throws an exception
throw new IndexOutOfBoundsException("Index out of bounds :"+ index); }}}Copy the code1.5.1 test
System.out.println("Initialize linear table with capacity 6===============>");
MyFinalArrayList<Object> objectMyFinalList = new MyFinalArrayList<>(6);
System.out.println("Insert elements ===============>");
objectMyFinalList.add(null);
objectMyFinalList.add(2);
objectMyFinalList.add("3");
objectMyFinalList.add("3");
objectMyFinalList.add(null);
objectMyFinalList.add("3");
// Try to add the seventh element, it will not succeed
objectMyFinalList.add("6");
// Outputs the inner elements
System.out.println(objectMyFinalList);
System.out.println("Get first element ===============>");
// Get the first element
Object o = objectMyFinalList.get();
System.out.println(o);
System.out.println("To get size = = = = = = = = = = = = = = = >");
/ / get the size
int size1 = objectMyFinalList.size();
System.out.println(size1);
System.out.println("Delete the first null element ===============>");
boolean delete = objectMyFinalList.delete(null);
System.out.println(delete);
System.out.println("再次获取size===============>");
int size2 = objectMyFinalList.size();
System.out.println(size2);
System.out.println("Delete specified index element ===============>");
Object delete1 = objectMyFinalList.delete(1);
// Index out of bounds
//objectMyFinalList.delete(7);
System.out.println(delete1);
System.out.println("再次获取size===============>");
int size3 = objectMyFinalList.size();
System.out.println(size3);
System.out.println("Set the element value of the specified index ===============>");
objectMyFinalList.set(0."Set value 1");
System.out.println("Get element value validation for this index ===============>");
Object o2 = objectMyFinalList.get();
System.out.println(o2);
System.out.println("Get the first index of the specified value ===============>");
int index = objectMyFinalList.indexOf("3");
System.out.println(index);
System.out.println("Output all elements ===============>");
System.out.println(objectMyFinalList);
System.out.println("再次获取size===============>");
int size4 = objectMyFinalList.size();
System.out.println(size4);
System.out.println("Contains ===============>");
System.out.println(objectMyFinalList.contains(null));
Copy the code2 linear list chain storage structure
2.1 Overview of linear table chain storage architecture
Due to the sequential nature of storing adjacent structural elements, there can be no free memory space in between. As a result, inserting and deleting elements next to each other involves moving a lot of elements around, which obviously takes time. Therefore, in order to reduce the time complexity of adding and deleting elements, we can consider the chain storage structure.
The chain storage structure of a linear table is characterized by an arbitrary set of storage units that store the data elements of a linear table. This set of storage units may be contiguous or discontiguous in memory space. This means that these data elements can exist anywhere memory is not occupied.
However, in order to ensure that elements in discontinuous space can find their precursor and successor, in the composition of chain structure elements, besides the information of data elements, the storage address of its successor or precursor elements should be stored.
We call the domain where data element information is stored data domain, and the domain where direct successor location is stored pointer domain. The information stored in a pointer domain is called a pointer or chain. These two pieces of information form a storage image of a data element, called a node.
N nodes are linked to form a linear list, also known as a linked list.
If a linked list contains only one pointer field per node, it is called a singly linked list. A singly linked list is simply a linear list of data elements linked together in their logical order through the pointer field of each node.
A linked list solves the problem of adding and deleting elements in an array, because to add or delete elements in a certain location, you only need to change the pointer of the adjacent element to the newly added element, without moving the element’s position.
2.2 a singly linked list
Here is the simplest operation of a single linked list.
2.2.1 Search of single linked list
In the sequential storage structure of a linear table, it is easy to calculate the storage location of any element. In a singly linked list, however, data is distributed, so if you want to access the data, you have to start with the first data and work your way down the pointer (this is called sequential access). Therefore, the operation of obtaining the ith element of a singly linked list is algorithmically more difficult.
The algorithm for obtaining the I th index data of linked list is as follows:
- To determine whether I crossing the line, I < 0 | | I > size, if the cross the throw an exception.
- Then declare a variable f to point to the first node in the list, and initialize j from zero in the loop;
- When j< I, the linked list is traversed, so that the pointer of is moved backward, constantly pointing to the next node, that is, f=f ext, and j increases by 1;
- When the loop ends, the variable f points to the ith index we’re looking for.
In other words, you start at the beginning, until you get to node I +1. We denoted the amount of data in the linked list as N. Since the time complexity of this algorithm depends on the position of I, when I =0, there is no need to traverse and the data is taken out at the first one, while when I =n, n-1 times is required. So the worst-case time is O(n). Such a search is also called a linear search.
2.2.2 Addition and deletion of single linked lists
- Inserts data at the specified index I
- To determine whether I crossing the line, I < 0 | | I > size, if the cross the throw an exception.
- Then find the element X of the original index I and the precursor element Y of the original index I by searching.
- Construct a new node Z, whose successors point to the original index element z.ext =x
- The successor of y, the precursor of the original index I, points to the new element, y.next=z
- Deletes data at the specified index I
- To determine whether I crossing the line, I < 0 | | I > size, if the cross the throw an exception.
- Then find the element X of the original index I, the precursor element Y of the original index I, and the successor element Z of the original index I.
- Let y next point to z, y.next=z
- Recovery of x
By analyzing the above single-linked list insertion and deletion algorithms, we find that they are actually composed of two parts: the first part is to traverse to find the I index node; The second part is inserting and deleting nodes.
We denoted the amount of data in the linked list as N, and only two Pointers need to be changed to insert and delete data, so the time spent is independent of N. If you have reached the point where you want to add data, the add operation takes O(1) time. Deleting data also takes O(1) time.
Although the initial search time is required, we assume that we need to insert 10 elements at index I, so for the sequential storage structure, it means that we need to move n-i-1 nodes every time we insert, and the time is O(n) each time. In a single linked list, we only need to find the pointer to the ith position, which is O(n) at the first time, and then simply move the pointer by assigning. For both insert and delete operations, the time complexity of the linked list is O(1). Obviously, the more frequently data is inserted or deleted, the greater the efficiency advantage of singly linked lists.
2.2.3 Simple implementation of single linked list
/** * simple single linked list implementation of linear list chain storage structure */
public class MySingleLinkedList<E> {
/** * empty constructor, internal nodes are not initialized, will be initialized at the first time added. * /
public MySingleLinkedList(a) {}/** * Number of elements */
private int size;
/** * a reference to the header */
private Node<E> first;
/** * nodes within a single list */
private static class Node<E> {
// Reference to the next node
Node<E> next;
// Node data
E data;
// Node constructor
public Node(E data, Node<E> next) {
this.data = data;
this.next = next; }}/** * adds elements to the end of a single list */ by default
public void add(E e) {
// Create a node
Node<E> newNode = new Node<>(e, null);
// If the header is not null
if(first ! =null) {
/* Find the last node */
Node f = first;
while(f.next ! =null) {
f = f.next;
}
f.next = newNode;
} else {
// If the header is null, then the new node is the first node, which is the header.
first = newNode;
}
size++;
}
/** * Removes the single linked list header element */ by default
public E remove(a) {
if (first == null) {
throw new NoSuchElementException();
}
// If the header is not null
E e = first.data;
first = first.next;
size--;
return e;
}
/** * add an element to the list to specify the index position, the original index node is linked to next */
public void add(E e, int index) {
checkPositionIndex(index);
// if index is 0
if (index == 0) {
first = new Node<>(e, first);
size++;
return;
}
// if index = 1
if (index == 1) {
first.next = new Node<>(e, first.next);
size++;
return;
}
if (index == size) {
add(e);
return;
}
// It is a header node for the time being. When the loop ends, it points to the index node
Node<E> x = first;
//index Indicates the previous node of the index
Node<E> y = null;
for (int i = 0; i < index; i++) {
x = x.next;
if (i == index - 2) { y = x; }}// Next points to the new node, and next points to the original index node
y.next = new Node<>(e, x);
size++;
}
/** * removes the element */ at the index position of the singly linked list
public E remove(int index) {
checkElementIndex(index);
if (index == 0) {
return remove();
}
// if index = 1
if (index == 1) {
E e = first.next.data;
first.next = first.next.next;
size--;
return e;
}
// For the time being, it is the head node. After the loop ends, it points to the next node of the node indexed by index
Node<E> x = first;
//index Indicates the previous node of the index
Node<E> y = null;
//index Indicates the index node
Node<E> z = null;
for (int i = 0; i <= index; i++) {
x = x.next;
if (i == index - 2) {
y = x;
}
if (i == index - 1) {
z = x;
}
}
y.next = x;
E e = z.data;
size--;
z = null;
return e;
}
/** * gets the number of elements */
public int size(a) {
return size;
}
@Override
public String toString(a) {
StringBuilder stringBuilder = new StringBuilder();
if (size > 0) {
Node<E> f = first;
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(f.data.toString());
if(i ! = size -1) {
stringBuilder.append(",");
}
f = f.next;
}
stringBuilder.append("]");
return stringBuilder.toString();
}
return "[]";
}
/** * check whether the index is out of bounds, used to delete, get */
private void checkElementIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds"); }}/** * check if the index is out of bounds and is used to add */
private void checkPositionIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds"); }}}Copy the code2.2.3.1 test
MySingleLinkedList<Object> objectMySingleLinkedList = new
MySingleLinkedList<>();
objectMySingleLinkedList.add(111);
objectMySingleLinkedList.add(222);
objectMySingleLinkedList.add(333);
System.out.println(objectMySingleLinkedList.remove(0));
objectMySingleLinkedList.add(444.0);
System.out.println(objectMySingleLinkedList);
Copy the code2.3 Static Linked lists
2.3.1 Overview of static linked lists
Has a pointer, for some high level language such as C, Java, C #, with indirect object reference implementation of the pointer, so you can use the pointer or object reference to build the implementation of the singly linked list, but for early senior programming language such as Basic, Fortran, because there is no pointer/object references, chain table structure according to the front of our way, It’s not going to work.
We can use the object array instead of pointer to realize the chain storage structure, we say the characteristics of the chain storage structure is that the storage location can not be adjacent, the logical relationship between the data can be described, as long as we use the array to achieve these two requirements, we can achieve the purpose of using the array to achieve the chain storage structure.
An object in an object array is a node in a linked list that contains two parts: a data field and a pointer field. Data field is to store objects, and this “pointer field” is actually stored in the next node of the array element subscript index, using the array subscript index cleverly as a pointer, to find the location of the next element, very clever.
To do the same thing as a single linked list, you can split the array into two parts, one for storing data and the other for standby free linked lists, which are both “logical linked lists”. Standby linked list, that is, linked to various free locations, when storing data, starting from the first free location in the free list; When deleting data, the data at the specified index is deleted. All you need to do is change the “pointer” — the subscript index — without moving any other elements.
To hold the array “datapool” and the “head pointer” — the starting index of the “free linked list”, we need two additional variables for storage.
2.3.2 Simple implementation of static linked list
/** * a simple implementation of a static list. For simplicity, the underlying array of this implementation is designed to be unextensible */
public class MyStaticLinkedList<E> {
/ * * * chain is realized by using an array of storage * /
private final Node<E>[] elements;
/** * Capacity */
private final int capcity;
/** * the header index of the linked list */
private int datafirst;
/** * the free list header index */
private int freefirst;
/** * Number of elements */
private int size;
/** * constructor */
public MyStaticLinkedList(int capcity) {
if (capcity <= 0) {
throw new IllegalArgumentException("Illegal Capacity: " +
capcity);
}
this.capcity = capcity;
this.elements = new Node[capcity];
}
/** * nodes within a single list */
private static class Node<E> {
// The reference to the next node, represented here by the array subscript index
Integer next;
// Node data
E data;
// Node constructor
private Node(E data, Integer next) {
this.data = data;
this.next = next;
}
@Override
public String toString(a) {
return "Node{" +
"next=" + next +
", data=" + data +
'} '; }}/** * Adds elements to the end of a single list * by default@paramE Element to be added *@returnTrue Add succeeded false Add failed */
public boolean add(E e) {
if (checkCapcity()) {
return false;
}
// Create a node
Node<E> newNode = new Node(e, null);
if (size == 0) {
elements[freefirst] = newNode;
freefirst = 1;
} else {
// Find the tail node
Node<E> firstNode = elements[datafirst];
while(firstNode.next ! =null) {
firstNode = elements[firstNode.next];
}
firstNode.next = freefirst;
elements[freefirst] = newNode;
// Find the next free list header
findFreeFirst();
}
size++;
return true;
}
/** * Removes the single linked list header element * by default@returnThe deleted element */
public E remove(a) {
if (size == 0) {
return null;
} else {
Node<E> first = elements[datafirst];
E e = first.data;
Integer nextIndex = first.next;
if (nextIndex == null) {
datafirst = 0;
freefirst = 0;
elements[datafirst] = null;
} else {
elements[datafirst] = null;
datafirst = nextIndex;
// Find the next free list header
findFreeFirst();
}
size--;
returne; }}/** * add an element to the list at the specified index position. The original index node is linked to next *@paramE Element to be added *@paramIndex Specifies the index *@returnTrue Add succeeded false Add failed */
public boolean add(E e, int index) {
checkPositionIndex(index);
if (checkCapcity()) {
return false;
}
if (index == size) {
add(e);
} else if (index == 0) {
// Create a node
elements[freefirst] = new Node<>(e, datafirst);
// Update the header of the linked list
datafirst = freefirst;
// Find the head of the next free list
findFreeFirst();
} else {
// Find the node that precedes the specified node
Node<E> preNode = getNode(index - 1);
// Create a node
elements[freefirst] = new Node<>(e, preNode.next);
// Change "index"
preNode.next = freefirst;
// Find the next free list header
findFreeFirst();
}
size++;
return true;
}
/** * removes the index element **@paramIndex Specifies the index *@returnThe deleted element */
public E remove(int index) {
checkElementIndex(index);
if (size == 0) {
return null;
} else if (index == 0) {
return remove();
} else {
// Gets the preceding element of the deleted element
Node<E> preNode = getNode(index - 1);
// Get the index of the current element
Integer nodeIndex = preNode.next;
Node<E> node = elements[nodeIndex];
E data = node.data;
// Change "pointer"
preNode.next = node.next;
// The deleted elements are left empty for GC to collect
elements[nodeIndex] = null;
// Adjust the header index of the free list
if (nodeIndex < freefirst) {
freefirst = nodeIndex;
}
size--;
returndata; }}/** * gets the element ** of the specified list index@paramThe index index *@returnThe element */ at the index
public E get(int index) {
checkElementIndex(index);
return getNode(index).data;
}
@Override
public String toString(a) {
if (size == 0) {
return "[]";
} else {
StringBuilder stringBuilder = new StringBuilder();
Node<E> node = elements[datafirst];
stringBuilder.append(node.data).append(",");
while(node.next ! =null) {
node = elements[node.next];
stringBuilder.append(node.data);
if(node.next ! =null) {
stringBuilder.append(","); }}returnstringBuilder.toString(); }}/*** * enhances toString for testing */
public String toStringAll(a) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < elements.length; i++) {
Node<E> node = elements[i];
if(node ! =null) {
stringBuilder.append(node.toString());
} else {
stringBuilder.append("null");
}
if(i ! = elements.length -1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
stringBuilder.append("{ freefirst:").append(freefirst);
stringBuilder.append(", datafirst: ").append(datafirst);
stringBuilder.append(", size: ").append(size).append("}");
return stringBuilder.toString();
}
/** * find the next free list header */
private void findFreeFirst(a) {
for (int i = 0; i < elements.length; i++) {
if (elements[i] == null) {
freefirst = i;
break; }}}/** * gets the node ** at the specified position@paramIndex Specifies the index *@returnNode * /
private Node<E> getNode(int index) {
/* Find the node */
Node<E> firstNode = elements[datafirst];
for (int i = 0; i < index; i++) {
firstNode = elements[firstNode.next];
}
return firstNode;
}
/** * check whether the index is out of bounds, used to delete, get */
private void checkElementIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds"); }}/** * check if the index is out of bounds and is used to add */
private void checkPositionIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds"); }}/** * Check the capacity */
private boolean checkCapcity(a) {
returnsize == capcity; }}Copy the code2.3.2.1 test
MyStaticLinkedList<Object> objectMyStaticLinkedList = new MyStaticLinkedList<>(6);
boolean add2 = objectMyStaticLinkedList.add(22);
boolean add3 = objectMyStaticLinkedList.add(33);
objectMyStaticLinkedList.remove();
System.out.println(objectMyStaticLinkedList);
boolean add4 = objectMyStaticLinkedList.add(44);
System.out.println(objectMyStaticLinkedList);
boolean add5 = objectMyStaticLinkedList.add("55");
boolean add6 = objectMyStaticLinkedList.add("66");
boolean add7 = objectMyStaticLinkedList.add("77");
boolean add8 = objectMyStaticLinkedList.add("88");
System.out.println(objectMyStaticLinkedList);
objectMyStaticLinkedList.remove();
System.out.println(objectMyStaticLinkedList);
boolean add9 = objectMyStaticLinkedList.add("99");
System.out.println(objectMyStaticLinkedList);
objectMyStaticLinkedList.remove();
System.out.println(objectMyStaticLinkedList);
System.out.println(objectMyStaticLinkedList.get(3));
System.out.println(objectMyStaticLinkedList.get(0));
System.out.println(objectMyStaticLinkedList);
objectMyStaticLinkedList.add(1.1);
System.out.println(objectMyStaticLinkedList);
Object remove = objectMyStaticLinkedList.remove(0);
System.out.println(remove);
System.out.println(objectMyStaticLinkedList);
Object remove2 = objectMyStaticLinkedList.remove(3);
System.out.println(remove2);
System.out.println(objectMyStaticLinkedList);
System.out.println(objectMyStaticLinkedList.toStringAll());
Copy the code2.4 Circular linked lists
We can also use a pointer at the end of a single list and make it point to the data at the head of the list, turning the list into a ring. This is called a circular list, also known as a circular list. Circular lists have no concept of heads and tails. Such lists are often used when you want to keep a fixed amount of up-to-date data.
Circular linked lists can solve a very troublesome problem: how to start from one of the nodes, access the list of all nodes.
Node ->next==NULL; node->next==NULL; The loop list determines that the end of the loop is (node->next) equal to the head. In fact, the circular list has no head nodes. The head node here is just an artificial marker. When traversing from the “head node”, if it returns to the “head node”, the circular list is finished.
To make it easier to iterate through a circular list, we can point to “tail nodes” instead of “head nodes”.
So you can access the top and bottom of the list in order one time.
Circular lists are actually quite simple, so again I won’t give the implementation examples.
2.5 Bidirectional linked lists
In a singly linked list, we have the next pointer, which makes it O(1) time to find the next node. But if we want to find the last node, the worst time is O(n), because we’re going to have to start from scratch every time.
To overcome the shortcoming of unidirectionality, we can set a node to have two Pointers, and make them point to the precursor node and the successor node respectively, which is the “bidirectional linked list”. With this list, you can easily traverse data not only from front to back, but also from back to front.
However, there are two disadvantages of bidirectional linked lists. First, the increase of Pointers will increase the storage space demand. Second, more Pointers need to be changed when adding and deleting data.
Our LinkedList collection in Java is a bidirectional list, so we are not implementing bidirectional lists again. This structure is also relatively simple, and you can quickly see how to implement it by looking at the source code for LinkedList.
Unidirectional cyclic linked lists are used to solve the problem of Joseph rings. Bidirectional lists can also have variants of circular lists, but are rarely used: the prev pointer to the header points to the tail, and the next pointer to the tail points to the header.
3 summary
This time mainly explains the basic principle of sequential storage structure and chained storage structure of linear list, and there are corresponding implementation cases, such as the realization of linear list, single Linkedlist, static Linkedlist, because Linkedlist is the realization of bidirectional Linkedlist, so it does not give the realization of bidirectional Linkedlist. As you can see, the linear table is a very simple data structure. In addition, there are stacks, queues and other special linear tables that have not been explained in this article, but will be explained next time.
Related articles:
- Big Talk Data Structure
- Diagram of algorithms
- My First Algorithm Book
If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!