The linear table
Directory:
- The linear table
- 1. Linear table abstract data types
- 2. Sequential representation and implementation of linear tables
- 2.1 Sequential storage structure of linear tables
- Table 2.2 order
- 2.3 Insertion and deletion of sequence tables
- 2.4 Shallow and deep copies of sequence tables
- 3. Chain representation and implementation of linear lists
- 3.1 a singly linked list
- 3.1.1 Nodes of a single linked list
- 3.1.2 Traversal operation of single linked list
- 3.1.3 Insertion operation of single linked list
- 3.1.4 Deleting a single linked list
- 3.1.5 Single linked list with nodes
- 3.1.6 Circular singly linked lists
- 3.2 double linked list
- 3.2 Circular double-linked lists
- 3.1 a singly linked list
1. Linear table abstract data types
A linear table is a linear structure with linear relations among its constituent elements. The basic operations of a linear table mainly include obtaining element values, traversing, inserting, deleting, searching, replacing and sorting, etc. The inserting and deleting can be carried out in any position of the linear table. Linear tables can be represented by sequential storage and chain storage structures.
The characteristics of a linear table are as follows: 1. There is only one start node, no direct precursor, and one direct successor; 2. There is only one end node, no direct successor, but one direct precursor; 3. All other nodes have a direct precursor and a direct successor.
A linear list is a finite sequence of n(n>=0) elements of the same type. This interface is actually a List, so why rewrite it instead of just pasting the JDK source code? When I was in an interview with Ali, the interviewer asked me: Did I rewrite some of the JDK source code by myself? Rewrite the source code to learn the underlying implementation.
Create a linear table interface llist.java with the following information:
public interface LList<T> {
/** void check method */
boolean isEmpty(a);
/** Linear table length */
int size(a);
/** returns the ith element */
T get(int index);
/** Sets the ith element to t*/
void set(int index,T t);
/** insert t as the ith element */
void insert(int index,T t);
/** Insert t*/ at the end of the linear table
void add(T t);
/** Removes the ith element */
T remove(int i);
/** Delete all elements */
void removeAll(a);
/ * * * /
T search(T key);
}
Copy the codeSince linear tables can be represented by sequential storage and chained storage structures, two implementation classes are created:
// Sequential storage
public class SequenceList<T> implements LList<T>
Copy the code// Chain storage structure
public class SinglyLinkedList<T> implements LList<T>
Copy the code2. Sequential representation and implementation of linear tables
2.1 Sequential storage structure of linear tables
Sequential storage of a linear table is to store the data elements of a linear table in sequence by a group of contiguous memory cells. The physical storage order of the elements in memory is the same as their logical storage in a linear table. This method is called a sequence list.
The storage address of the data element AI in a linear table is a linear function of its position I in the linear table. As shown in the figure:
Sequential tables usually use arrays to store data elements. The order of the data elements in a linear table is stored in an array. The total physical order of the array elements is the same as the order of the elements in a linear table. An array is a sequential storage random-access structure that occupies a contiguous set of storage cells. Elements are identified by subscripts (ordinals) whose addresses are linear functions of the subscripts. A subscript uniquely identifies an element, and the time it takes to access any element is ***O(1)***.
The SequenceList class implements the interface LList
public class SequentialList<T> implements LList<T> {
private Object[] element;
private int len;
public SequentialList(int size){
// If size<0, a negative length exception is thrown
this.element = new Object[size];
this.len = 0;
}
/** * The default length for creating containers */
public SequentialList(a) {
this(64);
}
// Time complexity is O(1)
@Override
public boolean isEmpty(a) {
return this.len == 0;
}
// Time complexity is O(1)
@Override
public int size(a) {
return this.len;
}
// Time complexity is O(1)
@Override
public T get(int index) {
if (index >= 0 && index < this.len){
return (T) this.element[index];
}
return null;
}
// Time complexity is O(1)
@Override
public void set(int index, T t) {
if (t == null) {return;
}
if (index >= 0 && index < this.len){
this.element[index] = t;
}else {
throw new IndexOutOfBoundsException(index+""); }}}Copy the codeInsert and delete operations on a sequential table move data elements.
Insert elements if the array is full, will not be inserted, will quote data exceptions (IndexOutOfBoundsException). The solution to data overflow is to expand the array. The JDK does this by applying a larger array and copying all its elements, thus expanding the size of the order table.
public class SequentialList<T> implements LList<T> {
// The time complexity is O(n)
public void insert(int index, T t) {
if (t == null) {return;
}
// If the array is full, expand the order table
if (this.len == element.length){
Object[] tmp = this.element;
this.element = new Object[tmp.length*2];
for (int i = 0; i<tmp.length; i++){this.element[i] = tmp[i]; }}// subscript tolerance
if (index < 0){
index = 0;
}
if (index > this.len){
index = this.len;
}
// Elements are moved back by len/2 on average
for (int i = this.len-1; i>=index; i--){this.element[i+1] = this.element[i];
}
this.element[index] = t;
this.len++;
}
public void add(T t) {
insert(this.len,t); }}Copy the codepublic class SequentialList<T> implements LList<T> {
public T remove(int i) {
if (this.len == 0 || i<0 || i >= this.len){
return null;
}
T old = (T) this.element[i];
for (intj = i; j<this.len-1; j++){this.element[j] = this.element[j+1];
}
this.element[this.len-1] = null;
this.len--;
return old;
}
public void removeAll(a) {
this.len = 0; }}Copy the codeA constructor of a class whose argument is the object is called a copy constructor. Such as:
Public Student (Student Student) {... }Copy the codeThe copy constructor copies the object, initializing the newly created object with the instance value of the formal parameter.
- Shallow copy of a sequential list: If a class implements a copy constructor as a field by field copy, assigning the values of the various member variables of the current object to the corresponding values of the actual parameters is called a shallow copy. Shallow copy constructors such as the SequentialList class:
public class SequentialList<T> implements LList<T> {
/** * shallow copy constructor */
public SequentialList(SequentialList<T> list){
this.element = list.element;
this.len = list.len; }}Copy the codeIn Java, when the data type is a basic type, shallow copy can realize the object copy function, array and class are reference types, assignment between two arrays/objects is reference assignment, array assignment does not apply for new storage space, and object assignment does not create new instances. So when the data type of a member variable is a reference type, shallow copy only copies the object reference and does not really implement the object copy function.
- Deep copy of sequential tables: When a class contains a member variable of a reference type, the copy constructor declared by that class not only copies all of the object’s primitive type member variable values, but also reclaims the dynamic storage occupied by the reference type variable and copies all of the objects in it. Deep-copy constructors such as the SequentialList class:
public class SequentialList<T> implements LList<T> {
/** * deep copy constructor */
public SequentialList(SequentialList<T> list){
this.len = list.len;
this.element = new Object[list.element.length];
for (int i = 0; i<list.element.length; i++){this.element[i] = list.element[i]; }}}Copy the codeConsider the problem of Joseph rings in combination with the characteristics of sequential tables
You have n people, you count in a circle, you count from s to M, you shoot one person, you keep counting from S to D, you shoot all of them. Outputs the order of death for all.
public class Josephus {
/ * * *@paramNumber Total number *@paramStart Start position *@paramDistance executes the position */
public Josephus(int number,int start,int distance){
SequentialList<String> list = new SequentialList<>(number);
for (int i= 0; i<number; i++){ list.add((char) ('A'+i)+"");
}
System.out.println("Joseph ring ("+number+","+start+","+distance+")");
System.out.println(list.toString());
int i = start;
while (list.size() > 1){
i = (i + distance-1)%list.size();
System.out.println("Delete"+list.remove(i).toString());
System.out.println(list.toString());
}
System.out.println("The person to be pardoned is."+list.get(0).toString());
}
public static void main(String[] args) {
new Josephus(5.0.2); }}Copy the codeThe chained storage of linear tables stores data elements in several storage units with scattered addresses. Logically adjacent data elements may not be physically adjacent. A storage unit that stores a data element contains at least two parts — a data domain and an address domain. The data domain stores the values of the data element, and the address domain stores the addresses of subsequent elements. A singly linked list is a chain of nodes, as shown in the figure below:
3.1.1 Nodes of a single linked list
A single linked list is made up of nodes. The difference between different linked lists is the difference between nodes. Declare a single-linked list class Node as follows:
public class Node<T> {
/** Data field, save the data element */
public T data;
/** address field, reference the next node, link the two nodes with the next chain */
public Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
public Node(a) {
this(null.null); }}Copy the codeThe data type of the member variable next is the Node class itself, which is called a self-referential class. A class declaration contains a member variable that refers to an object of the current class.
3.1.2 Traversal operation of single linked list
To traverse a single linked list is to visit each node in the single linked list, starting from the first node, along the next chain of the node, and visit each node only once.
Node<T> node = head;
while(node ! =null){
node = node.next;
}
Copy the codeThe statement node = node.next moves node to its successor node without changing the link between nodes. If you write “node.next = node”, node.next points to itself, changes the link relationship, and loses its successors, traversing becomes an infinite loop
3.1.3 Insertion operation of single linked list
To insert a single linked list, you only need to change the link relationship between nodes without moving data elements. Insert a node into a single linked list, according to the different position: empty table insert, head insert, middle insert, tail insert 1. Empty table insert, head insert
head = new Node<T>(t,head);
Copy the codeEmpty table inserts are also header inserts.
if(head == null) {// Insert an empty table
head = new Node<T>(t,null);
}else{
/ / insert
Node<T> node = new Node<T>(t,null);
node.next = head;
}
Copy the codeSuppose node points to a node in a non-empty singly linked list. Insert Q node after node
Node<T> node = new Node<T>(t,null);
q.next=node.next; // Q's successor is the original node's successor
node.next = q;//q is the new successor of node
Copy the codeIf node points to the last node, node.next == null, the above code block can be executed. The above code can also be reduced to one sentence:
p.next = new Node<T>(t,p.next);
Copy the code3.1.4 Deleting a single linked list
To delete a node in a singly linked list, you can change the link relationship between nodes by changing the next field of the node, without moving elements. 1. Delete the first node in a single linked list by making head point to the next node
head = head.next;
Copy the codeIf the single linked list has only one node, the single linked list becomes empty after the node is deleted.
3.1.5 Single linked list with nodes
A singly linked list of leading nodes adds a special node, called a header, before the first node in the singly linked list. The function of a header node is to make the head pointer of all linked lists (including empty tables) non-null, and to make the insertion and deletion operations of a single linked list do not need to be distinguished as empty tables or whether they are performed in the first position, so as to be consistent with the insertion and deletion operations of other positions.
public class SinglyLinkedList<T> implements LList<T> {
// a header pointer to a single-linked list header
public Node<T> head;
/** * overrides the default no-argument construct to construct a single linked list with a header, data and next are null */
public SinglyLinkedList(a) {
head = new Node<T>();
}
/** * shallow-copy constructor *@param list
*/
/*public SinglyLinkedList(SinglyLinkedList
list) { head = list.head; } * /
/** * deep copy constructor *@param list
*/
public SinglyLinkedList(SinglyLinkedList<T> list) {
this(a); Node<T> node = list.head.next; Node<T> rear =this.head;
while(node ! =null){
rear.next = new Node<T>(node.data,null); rear = rear.next; node = node.next; }}/** * Constructs a single linked list from multiple objects in the specified array, using tail insertion to construct a single linked list *@paramElement Data element */
public SinglyLinkedList(T[] element) {
this(a); Node<T> rear = head;for (int i = 0; i < element.length; i++) {
rear.next = new Node<T>(element[i],null); rear = rear.next; }}@Override
public boolean isEmpty(a) {
return head.next == null;
}
@Override
public int size(a) {
int i = 0;
Node<T> node = head.next;
while(node ! =null){
i++;
node = node.next;
}
return i;
}
@Override
public T get(int index) {
if (index >= 0){
Node<T> node = head.next;
for (int i = 0; node ! =null && i<index; i++) {
node = node.next;
}
if(node ! =null) {returnnode.data; }}return null;
}
@Override
public void set(int index, T t) {
if (t == null) {return;
}
if (index >= 0){
Node<T> node = head.next;
for (int i = 0; node ! =null && i<index; i++) {
node = node.next;
}
if(node ! =null){
node.data = t;
}else{
throw new IndexOutOfBoundsException(index+""); }}}@Override
public void insert(int index, T t) {
if (t == null) {return;
}
Node<T> node = head;
for (int i=0; node.next! =null&&index<i; i++){ node = node.next; } node.next =new Node<T>(t,node.next);
}
@Override
public void add(T t) {
insert(Integer.MAX_VALUE,t);
}
@Override
public T remove(int i) {
if (i >= 0){
Node<T> node = head;
for (int j = 0; node.next ! =null && j<i ; j++) {
node = node.next;
}
if(node.next ! =null){
T old = node.data;
node.next = node.next.next;
returnold; }}return null;
}
@Override
public void removeAll(a) {
head.next = null;
}
@Override
public T search(T key) {
//// is implemented in unit-10-search
return null;
}
@Override
public String toString(a) {
String string="(";
Node<T> node = this.head.next;
while(node ! =null) {
string += node.data.toString();
if(node.next ! =null){
string += ",";
}
node = node.next;
}
return string+")"; }}Copy the code3.1.6 Circular singly linked lists
The next chain of the last node of the list holds the head pointer value of the single list, forming a ring structure.
The construction method is:
public class CirSinglyLinkedList<T> {
public Node<T> head;
public CirSinglyLinkedList(a){
this.head = new Node<T>();
this.head.next = this.head;
}
public boolean isEmpty(a) {
return head.next == this.head;
}
@Override
public String toString(a) {
String string="(";
Node<T> node = this.head.next;
while(node ! =this.head) {
string += node.data.toString();
if(node.next ! =null){
string += ",";
}
node = node.next;
}
return string+")";
}
/ /... Other methods refer to singlyLinkedList.class
}
Copy the codeEach node of a double-linked list has two address fields, one pointing to its precursor node and the other to its successor node. The structure is as follows:
Create a double linked list base class:
public class DLinkNode<T> {
public T data;
public DLinkNode<T> prev,next;
public DLinkNode(T data, DLinkNode<T> prev, DLinkNode<T> next) {
this.data = data;
this.prev = prev;
this.next = next;
}
public DLinkNode(a) {
this(null.null.null); }}Copy the codeInsert and delete operations for double linked lists are different from those for single linked lists. Inserts a node into a double-linked list, either before or after the specified node.
// Insert q of x before node
q = new DLinkNode<T>(x,node.prev,node);
node.prev.next = q;
node.prev = q;
Copy the code// After the specified node is inserted, let's say q is inserted after node x
q = new DLinkNode<T>(x,node,node.next);
if(node.next ! =null) {// Execute during intermediate insertion
node.prev.next = q;
}
node.prev = q;
Copy the code2. Double linked list delete code is as follows:
node.prev.next = node.next;
if(node.next ! =null){
node.next.prev = node.prev;
}
Copy the code3.3 Circular double-linked lists
The next of the last node points to the header, and the prev chain of the header points to the last node. An empty double-linked list is one where the successor points to its own start node, and the start node points to its own successor.
The code is as follows:
public class CirDoublyLinkedList<T> implements LList<T> {
public DLinkNode<T> head;
public CirDoublyLinkedList(DLinkNode<T> head) {
this.head = new DLinkNode<T>();
this.head.prev = head;
this.head.next = head;
}
@Override
public boolean isEmpty(a) {
return head.next == null;
}
@Override
public int size(a) {
int i = 0;
DLinkNode<T> node = head.next;
while(node ! =null){
i++;
node = node.next;
}
return i;
}
@Override
public T get(int index) {
if (index >= 0){
DLinkNode<T> node = head.next;
for (int i = 0; node ! =null && i<index; i++) {
node = node.next;
}
if(node ! =null) {returnnode.data; }}return null;
}
@Override
public void set(int index, T t) {
if (t == null) {return;
}
if (index >= 0){
DLinkNode<T> node = head.next;
for (int i = 0; node ! =null && i<index; i++) {
node = node.next;
}
if(node ! =null){
node.data = t;
}else{
throw new IndexOutOfBoundsException(index+""); }}}/** * insert t into index node * time complexity is O(n) *@paramThe index node *@paramT * / object
@Override
public void insert(int index, T t) {
// Empty objects cannot be inserted
if (t == null) {return;
}
// Find the insertion position. When the loop stops, node points to index-1
DLinkNode<T> node = this.head;
for (int i = 0; node.next ! =this.head && i<index; i++){ node = node.next; }// Insert into node
DLinkNode<T> linkNode = new DLinkNode<T>(t,node,node.next);
node.next.prev = linkNode;
node.next = linkNode;
}
/** * Add node at the end of the loop double list * time complexity O(n) *@paramT * / object
@Override
public void add(T t) {
if (t == null) {return;
}
// Insert before the header
DLinkNode<T> linkNode = new DLinkNode<T>(t,head.prev,head);
head.next.prev = linkNode;
head.next = linkNode;
}
/** * delete node * with id = I@param i
* @return* /
@Override
public T remove(int i) {
if (i >= 0){
DLinkNode<T> node = this.head.next;
// Locate the node to be deleted
for (int j = 0; node ! = head&&j<i; j++){ node = node.next; }if(node ! = head){// Get the original object
T old = node.data;
node.prev.next = node.next;
// Delete node I
node.next.prev = node.prev;
returnold; }}return null;
}
@Override
public void removeAll(a) {
this.head.prev = head;
this.head.next = head;
}
@Override
public T search(T key) {
// Implemented in unit-10-search
return null; }}Copy the codeLink: document address source address