preface
Through the previous basic knowledge of data structure and algorithm we know some concepts and importance of data structure, so today we summarize the content related to linear tables. Of course, I use my own understanding to share with you.
In fact, to be honest, many people may still be confused about the difference and connection between a linear list, a sequential list, and a linked list!
- Linear table: logical structure, is the relationship between external exposure data, do not care about how to achieve the bottom layer, the logic structure of data structure classification is linear structure and nonlinear structure and sequence table, linked list is a linear table.
- Sequential list, linked list: physical structure, which is the implementation of a structure on the actual physical address of the structure. For example, sequential tables are implemented using arrays. Linked lists use Pointers to do the main work. Different structures are different in different scenes.
In Java, everyone knows the List interface type, which is the logical structure because it encapsulates a series of methods and data in a linear relationship. The actual implementation is all about the physical structure. For example, the contents of an ordered list are stored in an array, and a get, set, or add method is based on an array. A linked list is based on a pointer. When we think about data relationships in objects, we think about properties of Pointers. The point and value of a pointer.
The following diagram is used to analyze the relationship between linear tables. It may not be exact, but you can refer to it, and you will see examples from this diagram in the future.
Basic architecture of linear tables
For a linear table. Regardless of the actual implementation, the method function name and implementation effect should be the same (that is, the same method used, the same logical effect achieved, but the difference is the running efficiency). The concept of linear tables is somewhat similar to Java’s interface/abstract classes. The most famous are ArrayList and LinkedList of Lists. List is a logical structure that represents a linear List, while ArrayList and LinkedList are more of a physical structure (arrays and linked lists).
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(); int length(); boolean isEmpty(); // void elemIndex (T); // geteLem (int index) throws Exception; Void add(int index,T T) throws Exception; Void delete(int index) throws Exception; void add(T t) throws Exception; Void set(int index,T T) throws Exception; String toString(); // turn it into String}The order sheet
Sequential tables are implemented based on arrays, so all implementations need to be based on the array feature. For sequential table structures there should be an array of data to store the data and the effective use of length.
Another thing to note is the size of the initialized array. You can fix the size, but I will double it for availability if I run out of memory.
The following focuses on some beginners easy to confuse the concept and method implementation. Here the order table is likened to a team of men sitting on the bench.
The insert
add(int index,T t)
Where Index is the insertion number position, t is the inserted data, and the insertion process is as follows:
(1) Move one bit backward from the back (the last bit with data) to the index in order to clear the space of the index position
(2) Assign the value of the data to be inserted to the index position to complete the insertion operation
You can see that if the sequence list is long, at the very top if the insert is inefficient (insert time complexity is O(n)), and if the insert is frequent then the complexity is very high.
Delete operation
Similarly, deletions are very resource-intensive. To delete index, start at index+1 and assign data to the previous position. For details, see this picture:
Code implementation
Here I have implemented a sequence for your reference:
package LinerList; public class seqlist<T> implements ListInterface<T> { private Object[] date; Private int lensth; // private int lensth; Public seqList () {// Default size is 10 Init(10); } public void Init(int initSize) {this.date=new Object[initSize]; lenth=0; } public int length() { return this.lenth; } public Boolean isEmpty() {if(this.lentil ==0) return true; return false; Public int 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; } /* * 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) throws Exception {// Add (LENTH, T); } public void add(int index, int index, int index); T T) throws the Exception {the if (index < 0 | | index > lenth) throw new Exception (" numerical cross-border "); IF (ENTH == DATE.LENGTH) {newDate []= new Object[]; 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 ++]; } lenth--; // Override public void set(int index, 1); 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; }}The list
When learning C/C ++ linked lists should be a lot of people feel confused, this is a big reason may be because of Pointers, although Java does not use Pointers directly, but we also need to understand the principle and use of Pointers. Unlike sequential lists (arrays), linked lists are structured like a chain linked into a linear structure, and each node in the list has a different address. You can think of a linked list as it stores the address of the node (region), and you can find the corresponding node by using this pointer.
In the case of a physical storage structure, the connection between addresses cannot be changed. Neighbors are neighbors. But with chained storage, the address of the next bit is actively recorded by the previous one and can be changed. This is like brothers from birth are brothers with the same surname, and our best friends in the process of growing up may be due to stage changes!
Just like the Tang Monk, Wukong, Bajie, and the Sha Monk who went to the west for sutras. They have no contact, but sworn brothers, you ask Wukong his master it will immediately think of Tang Priest, because of the agreement under the Five Finger Mountain.
The basic structure
For linear tables, we only need a data array and length to represent the basic information. For the linked list, we need a node(head node), and length represent the stored node data and the length of the linked list, respectively. This node has a data field and a pointer field. The data field is to store the real data, while the pointer field is to store the pointer of the next node, and its specific structure is:
class node<T>{ T data; // the result of the node next; Public node(){} public node(T data) {this.data=data; } public node(T data, node next) { this.data = data; this.next = next; }}Leader-linked lists VS no leader-linked lists
A lot of people don’t know the difference between a leading node and a non-leading node, or even what a leading node is and a non-leading node, but let me explain this to you:
Lead node: The head pointer always points to a node that does not store valid values and only serves as an identifier (equivalent to the head teacher leading the students).
No lead node: The head pointer always points to the first valid node, which stores a valid value.
So what’s the difference between a leading node and a list without a leading node?
Search: no big difference, the lead node need to find one more time.
INSERT ON: No difference between the 0 position insert, no lead node inserted at 0 position after the need to change the point of the head.
Delete: Deleting a position other than 0 makes no difference. Deleting position 0 without a lead node requires redirecting the head.
Header deletion (lead node) : The deletion of the lead node is the same as a normal deletion. Head.next =head.next. Next, so head.next points directly to the second element. The first one was deleted
Header deletion (no lead node) : The first node (HEAD) without the lead node stores valid data. Instead of deleting the head node, it’s easy to simply point the head to the second node in the list. Namely: the head = head. Next
To sum up: the lead node through a fixed header can make any node in the linked list are equally inserted, deleted. A linked list without a head node requires special treatment when inserting, deleting position 0, and finally changing the head point. The difference between the two is to insert and delete the first place (especially insert) and of course I would recommend that you use the first place of a linked list as much as possible in the future to avoid unnecessary trouble.
Leading Pointer vs. Trailing Pointer
So basically a linked list is going to have a head pointer, so what’s a head and tail pointer?
Head Pointer: The head pointer is the head node in the linked list, called the head pointer.
The tail pointer: A tail pointer is a list with an extra tail node. The advantage of a tail pointer is that it can be inserted directly after the tail pointer, and then the order of the tail Pointers can be changed.
However, a single linked list with a tail pointer is not efficient if the tail is removed. You need to enumerate the entire list to find the node before tail for deletion.
The insert
Add (int index,T T) where index is the number position inserted,T is the number of data inserted, insert in the linked list of the lead node anywhere is equivalent. Add and insert a node node, find the previous node according to the index called pre. Then the operation flow is as follows
1. 'node.next=pre. Next', connect the inserted node with the corresponding part of the linked list first. Node. next is the same as pre-. next. 2. 'pre. Next =node' Insert node nodes into the linked list.
Of course, a lot of times the list needs to be inserted at the end of the list, and if you insert it frequently at the end of each enumeration, it might be inefficient, and you might use a tail pointer to do that.
Delete operation
DELETE (int index) DELETE (int index)
This method is a general method for the linked list of the lead node (including the deletion of the end). Find the previous node of the index (pre), pre. Next =pre. Next. Next
Code implementation
Here I also achieve a single linked list for you as a reference:
package LinerList; class node<T>{ T data; // the result of the 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); 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 current location 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; Team. Next =node; team. Next =node; Length++; // 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 current location node for(int I =0; i<index; I++)// mark the node before team {team=team.next; } // Team. Next node is the node we want to remove Team. Next = Team. Next. 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 current location 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; }}conclusion
You may ask if this is true, so let me test it out:
This is just a simple implementation, implementation of the basic method. A linked list is just a single linked list. The degree of perfection can be optimized. Limited ability, if there is a mistake or optimization of the place also ask the boss to correct.
Single-linked list queries are slower because they need to traverse from the beginning. If inserted at the end, consider designing a linked list with a tail pointer. Although the order table query speed is fast but insert is very time-consuming and laborious, the actual application according to the needs of the choice!
ArrayList and LinkedList in Java are examples of both approaches, but LinkedList uses bi-directional list optimization, and the JDK does a lot of optimization as well. So we do not have to make wheels, can be directly used, but handwritten order table, single linked list is still very valuable to learn.
Single linked list understand, double linked list is not far away (next episode trailer)!
Original official account:
bigsai
The article has been included in
The whole network is concerned about the data structure and algorithm learning warehouseWelcome to star