Abstract: In fact, to tell the truth, many people may still be confused between linear list, sequential list, and linked list between the difference and contact!

This article is shared by Huawei cloud community “Programmers must design their own linear tables (sequential lists, linked lists)”, original author: Bigsai.

preface

In fact, to tell the truth, many people may still be confused between linear list, sequential list, and linked list between the difference and contact!

  • Linear list: logical structure, is the relationship between external exposed data, do not care about how to achieve the bottom, the logical structure of data structure is linear structure and nonlinear structure and sequence list, linked list is a linear list.

  • Sequential list, linked list: physical structure, which is to implement a structure on the actual physical address of the structure. For example, sequential lists are implemented in arrays. Linked lists do most of the work with Pointers. Different structures have different differences in different scenes.

In Java, you know the List interface type, which is a logical structure because it is a set of methods and data that encapsulates a linear relationship. The concrete implementation is all about the physical structure. For example, the contents of a sequential list are stored in arrays, and the get, set, and add methods are all based on arrays, whereas linked lists are based on Pointers. When we think about data relationships in objects, we think about the properties of Pointers. The point and value of a pointer.

Here is a diagram to analyze the relationship of linear tables. It may be a little sketchy, but you can refer to it, and I’ll use it as an example later.

Basic architecture of linear tables

For a linear table. Regardless of how it is implemented, their method function names and implementation effects should be the same (that is, the use of the same method, to achieve the same effect logically, but the difference is the efficiency of the operation). The concept of linear tables is somewhat similar to Java’s interface/abstract classes. The most famous ones are Arraylist and LinkedList of lists. List is a logical structure that represents this structure as a linear List, while Arraylist and LinkedList are more of a physical structure (array and LinkedList).

So based on the object-oriented programming thought, linear table can be written as an interface, and the order of the specific implementation of table and linked list class can implement the linear table method, improve the readability of the program, there is a little more important, remember when beginners data structure and algorithm implement linear table are fixed type (int), with the progress of knowledge, We should use generics to make it more reasonable. The specific design of the interface is as follows:

package LinerList; public interface ListInterface<T> { void Init(int initsize); Int length(); boolean isEmpty(); Int ElemIndex(T T); T getElem(int index) throws Exception; Void add(int index,T T) throws Exception; // Obtain data according to index. Void delete(int index) throws Exception; // Insert data according to index. void add(T t) throws Exception; // Insert void set(int index,T T) throws Exception; String toString(); // convert to String}Copy the code

The order sheet

Sequential tables are implemented based on arrays, so all implementations need to be based on array features. The structure of the sequential table should have an array of data to store the data and use length effectively.

Another thing to note is the size of the initialization array. You can fix the size, but I’ll double it for usability if I run out of memory.

The following focuses on some concepts and method implementations that may be confusing for beginners. Here the sequence table is compared to a team of people sitting on a bench.

The insert

add(int index,T t)

Where index is the number of the inserted position, t is the inserted data, and the insertion process is as follows:

(1) Move one bit from the back (the last data bit) to the back of the index to vacate the space of the index position

(2) Assign the data to be inserted to index position to complete the insertion operation

It can be seen that if the order list is very long, if the insertion efficiency is relatively low in the early place (insertion time complexity is O(n)), and if the insertion is frequent, the complexity is quite high.

Delete operation

In the same way, deleting is very resource-intensive. Index +1: index+1: index+1: index+1

Code implementation

Here I implement a sequence table for you to learn as a reference:

package LinerList; public class seqlist<T> implements ListInterface<T> { private Object[] date; Private int lenth; Public seqList () {// Initial size defaults to 10 Init(10); } public void Init(int initsize) {// Initialize this.date=new Object[initsize]; lenth=0; } public int length() { return this.lenth; } public Boolean isEmpty() {if(this.lenth==0) return true; return false; } /* * * @elemIndex (t t) {// TODO auto-generated method stub for(int I =0; i<date.length; i++) { if(date[i].equals(t)) { return i; } } return -1; } /* * Obtain the number of elements */ public T getElem(int index) throws Exception {// TODO auto-generated method stub If (index < 0 | | index > lenth - 1) throw new Exception (" numerical cross-border "); return (T) date[index]; } public void add(T T) throws Exception {// Insert add(lenth, T); } public void add(int index, int index) T T) throws the Exception {the if (index < 0 | | index > lenth) throw new Exception (" numerical cross-border "); If (lenth==date.length)// Expand {Object newDate []= new Object[lenth*2]; for(int i=0; i<lenth; i++) { newdate[i]=date[i]; } date=newdate; } for(int i=lenth-1; i>=index; {date[I +1]=date[I]; } date[index]=t; // insert element lenth++; / / order table length + 1} public void the delete (int index) throws the Exception {the if (index < 0 | | index > lenth - 1) throw new Exception (" numerical cross-border "); for(int i=index; i<lenth; {date[I]=date[I +1]; } lenth--; } @override public void set(int index, T T) throws the Exception {the if (index < 0 | | index > lenth - 1) throw new Exception (" numerical cross-border "); date[index]=t; } public String toString() { String vaString=""; for(int i=0; i<lenth; i++) { vaString+=date[i].toString()+" "; } return vaString; }Copy the code

The list

Learning C/C ++ when linked list should be a lot of people feel very round things, this is a big reason may be because Pointers, although Java does not directly use Pointers but we also need to understand the principle and use of Pointers. The structure of a linked list is different from that of a sequential list (array), which is linked into a linear structure like a chain. Each node in a linked list has a different address. A linked list can be understood as storing the address pointing to a node (region), and the corresponding node can be found through this pointer.

For physical storage structures, the relationship between addresses cannot be changed; adjacent addresses are adjacent. But for chained storage, the next bit’s address is actively recorded by the previous one and can be changed. It’s like brothers are born with the same family name, and our best friends may have some changes in the course of growing up!

Just like the Buddhist monks tang Seng, Wukong, Bajie and Sha who went to the West for buddhist scriptures. They had no connection, but became sworn brothers as master and apprentice. If you ask Wukong his master, he will immediately think of Tang Priest because of the agreement at the foot of the Five fingers Mountain.

The basic structure

For linear tables, we only need a data array and length to represent basic information. For linked lists, we need a node(head), and length to represent the stored node data and linked list length, respectively. This node has a data field and a pointer field. A data field stores real data, while a pointer field stores a pointer to the next node. Its specific structure is:

class node<T>{ T data; // Node next; Public node(){} public node(T data) {this.data=data; } public node(T data, node next) { this.data = data; this.next = next; }}Copy the code

Leading node linked list VS unleading node linked list

A lot of people don’t know the difference between a linked-list with a leading node and a linked-list without a leading node, or even what is a linked-list with a leading node and a linked-list without a leading node.

Head node: The head pointer always points to a node that stores no valid values and serves only as an identifier.

Unheaded node: The head pointer always points to the first valid node, which stores the valid value.

So what’s the difference between a list with a leading node and a list without a leading node?

Search: no big difference, the lead node need to find a more.

Insert on: there is no difference between inserting at position 0 and not leading node. After inserting at position 0, the head should be changed again.

Delete on: there is no difference between deleting position 0 and not leading node. After deleting position 0, change the direction of head again.

Header deletion (lead node) : The deletion of the lead node is the same as normal deletion. Next = head.next-next, so head.next points directly to the second element. The first one was deleted

Header deletion (no leading node) : The first node (head) without a leading node stores valid data. It is also easy to remove the head without removing the lead node. Simply point the head to the second node in the list. Namely: the head = head. Next

To sum up: the leading node can be inserted and deleted equally for any node in the list through a fixed head. A list without a head node needs special treatment when inserting and deleting position 0, and finally changing the head pointer. The difference between the two is insertion and deletion of the first node (especially insertion). However, I recommend that you use the list of the first node in the future to avoid unnecessary trouble.

Leading pointer VS trailing pointer

Basically a linked list requires a header pointer, so what is a header pointer?

Header pointer: The header pointer is the head node in the linked list.

Tail pointer: A tail pointer is a linked list with one more tail node. The tail pointer can be inserted directly after the tail pointer, and then change the order of the tail pointer.

For a single linked list with a tail pointer, it is not efficient to delete the tail. You need to enumerate the entire list to find the node before tail.

The insert

add(int index,T t)

Where index is the number position of insertion, t is the data of insertion, and insertion at any position in the linked list of the lead node is equivalent. Insert a node (node, index) and find the previous node called pre. Then the operation flow is

1. 'node.next=pre. Next', connect the insert node to the corresponding part of the list first. Node. next is the same as pre-next. 2. 'pre. Next =node' inserts node into the linked list.Copy the code

Of course, most of the time, linked lists need to be inserted in the tail, if frequently inserted in the tail of each enumeration to the tail may be inefficient, may use a tail pointer to achieve tail insertion.

Delete operation

Delete (int index)

Next = pre-.next. Next = pre-.next-next

Code implementation

Here I also implement a single linked list for you to use as a reference:

package LinerList; class node<T>{ T data; // Node next; Public node(){} public node(T data) {this.data=data; } public node(T data, node next) { this.data = data; this.next = next; } } public class Linkedlist<T> implements ListInterface<T>{ node head; private int length; public Linkedlist() { head=new node(); length=0; } public void Init(int initsize) { head.next=null; } public int length() { return this.length; } public boolean isEmpty() { if(length==0)return true; else return false; } / / public int ElemIndex(T T) {node team=head.next; int index=0; while(team.next! =null) { if(team.data.equals(t)) { return index; } index++; team=team.next; } return -1; } @override public T getElem(int index) throws Exception {node team=head.next; If (index < 0 | | index > length - 1) {throw new Exception (" numerical cross-border "); } for(int i=0; i<index; i++) { team=team.next; } return (T) team.data; } public void add(T t) throws Exception { add(length,t); } // Insert the lead node, Public void add(int index, T value) throws the Exception {the if (index < 0 | | index > length) {throw new Exception (" numerical cross-border "); } node<T> team=head; //team finds the current position node for(int I =0; i<index; i++) { team=team.next; } node<T>node =new node(value); // Create a new node node.next=team.next; // the next pointer to the index position team.next=node; Length++; } @ Override public void the delete (int index) throws the Exception {the if (index < 0 | | index > length - 1) {throw new Exception (" numerical cross-border "); } node<T> team=head; //team finds the current position node for(int I =0; i<index; I++)// mark the previous node of team {team=team.next; } // the team.next node is the node we want to delete. length--; } @Override public void set(int index, T T) throws the Exception {/ / TODO Auto - generated method stub the if (index < 0 | | index > length - 1) {throw new Exception (" numerical cross-border "); } node<T> team=head; //team finds the current position node for(int I =0; i<index; i++) { team=team.next; } team.data=t; } public String toString() {String va=""; node team=head.next; while(team! =null) { va+=team.data+" "; team=team.next; } return va; }}Copy the code

conclusion

You may ask if this is true, so let me test it:

This is just a simple implementation, implementing the basic method. A linked list is just a single linked list. The degree of perfection can be optimized. Limited ability, if there are mistakes or optimization of the place also please big boss correct.

Single-linked list queries are slow because they need to be iterated from the beginning. If you insert at the end, you can consider a linked list with a tail pointer. Although the order table query speed is fast but the insertion is very time-consuming and laborious, the actual application according to the needs of choice!

Arraylist and LinkedList in Java are examples of both approaches, but LinkedList uses bidirectional list optimization, and the JDK does a lot of it. So you don’t have to build wheels, you can use them directly, but handwritten order lists, single linked lists are still very valuable to learn.

Click to follow, the first time to learn about Huawei cloud fresh technology ~