Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "what is a linear table, sequence list and linked list". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

First, let's take a look at the differences and relationships between linear tables, sequential lists, and linked lists:

Linear table:

Logical structure, which exposes the relationship between data, does not care how to realize the bottom layer. The logical structure of data structure is classified into linear structure and nonlinear structure, while sequential list and linked list are all linear tables.

The data stored in the linear table structure can often be arranged in turn, just like children holding hands. There is only one child holding hands with each student in front and behind. Data with this "one-to-one" relationship can be stored using linear tables.

Sequential list, linked list: physical structure, which implements a structure on the actual physical address. For example, a sequence table is implemented in an array. The linked list uses pointers to complete the main work. Different structures are different in different scenes.

Linear table

We first define an abstract class of a linear table, which mainly includes adding, searching, deleting and so on. The sequence list and linked list are used to implement the following:

/ * * Linear table * * @ author ervin * @ Date 2021-4-18 * / public interface ListInterface {/ * * initialize * @ param size * / void init (int size); / * * length * @ return * / int length (); / * * whether it is empty * @ return * / boolean isEmpty () / * get element subscript * @ param t * @ return * / int eleIndex (T t); / * get data according to index * @ param index * @ return * @ throws Exception * / T getEle (int index) throws Exception / * * insert data according to index * @ param index * @ param t * @ throws Exception * / void add (int index,T t) throws Exception; / * Delete elements * @ param index * @ throws Exception * / void delete (int index) throws Exception / * * insert element * @ param t * @ throws Exception * / void add (T t) throws Exception; / * modify * @ param index * @ param t * @ throws Exception * / void set (int index,T t) throws Exception;} sequence table

The sequential table is based on the array, because the data in the array is stored in a continuous memory, inserting and deleting elements will lead to the movement of some elements, which is inefficient, but the query efficiency is very fast.

Sequence table elements insert footprint:

Here we take insertion as an example, and the deletion operation is just the opposite.

If you want to delete an element with subscript 2, move the element with subscript 2 and later, from left to right, one bit to the left.

In addition, the insertion of sequential tables needs to consider "expansion".

Code implementation:

/ * * author ervin * @ Date 2021-4-18 * / public class SeqList implements ListInterface {/ / Array stores data private Object [] date; private int length; public SeqList () {/ / initial size defaults to 10 init (10);} @ Override public void init (int initSize) {this.date = new Object [initSize]; length = 0 } @ Override public int length () {return this.length;} @ Override public boolean isEmpty () {/ / is empty return this.length = = 0;} @ Override public int eleIndex (T t) {for (int I = 0; I)

< date.length; i++) { if (date[i].equals(t)) { return i; } } return -1; } @Override public T getEle(int index) throws Exception { if (index < 0 || index >

Length-1) {throw new Exception ("numerical out of bounds");} return (T) date [index];} @ Override public void add (T) throws Exception {/ / tail insert add (length, t);} @ Override public void add (int index, T) throws Exception {if (index)

< 0 || index >

Length) {throw new Exception ("numerical out of bounds");} / expand if (length = = date.length) {Object [] newDate = new Object [length * 2]; for (int I = 0; I

< length; i++) { newDate[i] = date[i]; } date = newDate; } //后面元素后移动 for (int i = length - 1; i >

= index; iMurt -) {date [I + 1] = date [I];} / / insert element date [index] = t; length++;} @ Override public void delete (int index) throws Exception {if (index)

< 0 || index >

Length-1) {throw new Exception ("numerical out of bounds");} / / move for before the element after index (int I = index; I)

< length; i++) { date[i] = date[i + 1]; } length--; } @Override public void set(int index, T t) throws Exception { if (index < 0 || index >

Length-1) {throw new Exception ("numerical out of bounds");} date [index] = t;}} linked list

The space in which linked lists store data is discontiguous. There are "node" linked together to form a linked list. Each "node" stores not only the data itself, but also the address of the next "node".

As shown in the figure:

Linked list to find elements, need to traverse search, low efficiency; insert and delete elements, only need to modify the pointer, very efficient.

Linked list does not need to consider "expansion"

The insertion of linked list elements indicates:

Schematic diagram for deletion of linked list elements:

Code implementation:

/ * * author ervin * @ Date 2021-4-18 * / public class LinkList implements ListInterface {private static class Node {T item; Node next; Node (T element, Node next) {this.item = element; this.next = next;}} Node header; private int size Public LinkList () {this.header = new Node (null,null); this.size = 0;} @ Override public void init (int size) {} @ Override public int length () {return this.size;} @ Override public boolean isEmpty () {return this.length () = = 0;} @ Override public int eleIndex (T t) {Node n = header.next Int index = 0; while (n.next! = null) {if (n.item.equals (t)) {return index;} index++; n = n.next;} / / cannot return-1 return-1 } @ Override public T getEle (int index) throws Exception {Node n = getNode (index); return (T) n.item;} @ Override public void add (int index, T) throws Exception {/ / consider the first element if (index = = 0) {this.header.next = new Node (t index null);} else {Node n = getNode (index-1) / / get the previous element n of index, which points to the newly created element, and the newly created element points to the next element of n, n.next = new Node (tmemn.next);} this.size++ } @ Override public void delete (int index) throws Exception {/ / index is 0, you don't have to get the previous element, if (index = = 0) {this.header.next = getNode (1);} else {Node n = getNode (index-1); n.next = n.next.} size-- } @ Override public void add (T t) throws Exception {add (size,t);} @ Override public void set (int index, T t) throws Exception {Node node = getNode (index); node.item = t;} private Node getNode (int index) throws Exception {if (index this.size-1) {throw new Exception ("Array out of bounds") } Node n = header.next; for (int I = 0 Bisti

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.