There are roughly four basic logical structures for the data after the application:

  • Collection: Data elements can only be in a “same collection” relationship
  • Linear structure: There is a one-to-one relationship between data elements
  • Tree structure: There is one pair of relationships between data elements
  • Graph structure or mesh structure: There are many to many relationships between data elements

For different logical structures of data, computers usually have two types of in-room storage structures on physical disks

  • Sequential storage structure
  • Chain storage structure

This post focuses on linear structures, which are mostly linear tables, and nonlinear structures, which are mostly trees and graphs. Basic features of linear tables: \

  • There is always a unique first data element
  • There is always a unique last data element
  • Each data element in the collection, except the first, has only one precursor data element
  • Each data element in the collection has only one subsequent data element except the last one

1. Sequential storage structure of a linear table: a group of storage cells with consecutive addresses are used to store the elements of a linear table at a time. To implement linear tables using sequential structures, programs often use arrays to store elements in a linear, random-stored data structure that is suitable for random access. The ArrayList class in Java is an array implementation of a linear table.

 

1 import java.util.Arrays; 2 public class SequenceList<T> 3 { 4 private int DEFAULT_SIZE = 16; 5 // Save the array length. 6 private int capacity; 8 Private Object[] elementData; Private int size = 0; private int size = 0; Public SequenceList() 13 {14 Capacity = DEFAULT_SIZE; 15 elementData = new Object[capacity]; Public SequenceList(T element) 19 {20 this(); 21 elementData[0] = element; 22 size++; 26 * @param element Specifies the first element in the list. 27 * @param initSize Specifies the length of the underlying array in the list. 28 */ 29 public SequenceList(T element , int initSize) 30 { 31 capacity = 1; 33 While (capacity < initSize) 34 {35 Capacity <<= 1; 36 } 37 elementData = new Object[capacity]; 38 elementData[0] = element; 39 size++; 42 public int length() 43 {44 return size; 45} 46 / / in the table for order linear index for the element I 47 public T get (int I) 48 {49 if (I < 0 | | I > size - 1) 50 {51 throw new IndexOutOfBoundsException (linear table index "cross-border"); 52 } 53 return (T)elementData[i]; 58 public int locate(T element) 57 {58 for (int I = 0; i < size ; i++) 59 { 60 if (elementData[i].equals(element)) 61 { 62 return i; 63 } 64 } 65 return -1; // Inserts an element at the specified position in the sequential linear list. 68 public void insert(T element , Int index) 69 {70 if (index < 0 | | index > size) 71 {72 throw new IndexOutOfBoundsException (linear table index "cross-border"); 73 } 74 ensureCapacity(size + 1); 75 // Move all elements after index back one space. 76 System.arraycopy(elementData , index , elementData 77 , index + 1 , size - index); 78 elementData[index] = element; 79 size++; 80} 81 // Add an element at the beginning of the linear order list. 82 public void add(T element) 83 { 84 insert(element , size); 85} 86 // Very troublesome, 87 private void ensureCapacity(int minCapacity) 88 {89 private void ensureCapacity(int minCapacity) 88 {89 if (minCapacity > capacity) 91 { 93 while (capacity < minCapacity) 94 {95 capacity <<= 1; 96 } 97 elementData = Arrays.copyOf(elementData , capacity); 98} 99} 100 / / delete order linear the element at the specified index in the table of 101 public T delete (int index) 102 103 if {(index < 0 | | index > size - 1), 104 {105 Throw new IndexOutOfBoundsException (linear table index "cross-border"); 106 } 107 T oldValue = (T)elementData[index]; 108 int numMoved = size - index - 1; 109 if (numMoved > 0) 110 { 111 System.arraycopy(elementData , index+1 112 , elementData, index , numMoved); ElementData [--size] = null; 116 return oldValue; 119 public T remove() 120 {121 return delete(sie-1); 123 public Boolean empty() 123 {126 return size == 0; 132 Array. fill(elementData, null); 133 size = 0; 134 } 135 public String toString() 136 { 137 if (size == 0) 138 { 139 return "[]"; 140 } 141 else 142 { 143 StringBuilder sb = new StringBuilder("["); 144 for (int i = 0 ; i < size ; i++ ) 145 { 146 sb.append(elementData[i].toString() + ", "); 147 } 148 int len = sb.length(); 149 return sb.delete(len - 2 , len).append("]").toString(); 150} 151} 152}Copy the code

 

2. Linear table chain storage structure: a set of addresses of arbitrary storage units will be used to store the data elements in a linear table. The linked list can be divided into: \

  • Singly linked list: Each node keeps only one reference to the next node of the current node, no reference to the head node, and null next reference to the tail node.
  • Circular list: A linked list connected end to end.
  • Bidirectional linked lists: Each node has two references, one to the node above the current node and one to the node next to the current node.

Java LinkedList is the implementation of a linear list, is a two-way LinkedList.

1 public class DuLinkList<T> 2 {3 public class DuLinkList<T> 2 {3 4 private class Node 5 {6 private T data; 9 private Node prev; 11 private Node next; 11 Private Node next; 13 public Node() 14 {15} 16 public Node(T data, Node prev, Node next) 18 { 19 this.data = data; 20 this.prev = prev; 21 this.next = next; 25 private Node header; 27 private Node tail; 29 private int size; 30 / / create an empty list of 31 public DuLinkList (32) {/ / empty lists 33, the header and tail are null 34 header = null; 35 tail = null; 38 public DuLinkList(T element) 39 {40 header = new Node(element, null, null); 41 // There is only one node. Header and tail point to this node. 43 size++; 46 public int length() 47 {48 return size; Public T get(int index) 53 {54 return getNodeByIndex(index).data; 55} 56 / / 57 private index access to specify the location of the nodes in the index Node getNodeByIndex (int index) 58 59 {the if (index < 0 | | index > size - 1) 60 { 61 throw new IndexOutOfBoundsException (linear table index "cross-border"); 62} 63 if (index <= size / 2) 64 {65 Node current = header; 67 for (int i = 0 ; i <= size / 2 && current ! = null 68 ; i++ , current = current.next) 69 { 70 if (i == index) 71 { 72 return current; 73} 74} 75} 76 else 77 {79 Node current = tail; 80 for (int i = size - 1 ; i > size / 2 && current ! = null 81 ; i++ , current = current.prev) 82 { 83 if (i == index) 84 { 85 return current; 86 } 87 } 88 } 89 return null; 95} 95 public int locate(T element) 93 {95 95 Node current = header; 96 for (int i = 0 ; i < size && current ! = null 97 ; i++ , current = current.next) 98 { 99 if (current.data.equals(element)) 100 { 101 return i; 102 } 103 } 104 return -1; // Insert an element at the specified position in the linear chained list. 107 public void insert(T element , Int index) 108 {109 if (index < 0 | | index > size) 110 {111 throw new IndexOutOfBoundsException (linear table index "cross-border"); If (header == null) 115 {116 add(element); 117} 118 else 119 {120 if (index == 0) 122 {123 addAtHeader(element); 124} 125 else 126 {128 Node prev = getNodeByIndex(index -1); 130 Node next = prev.next; 132 Node newNode = newNode (element, prev, next); // Make prev next point to the new node. 134 prev.next = newNode; 136 next. Prev = newNode; 137 size++; // Add new nodes to the list using the tail interpolation method. 142 public void add(T element) 143 {144 if (header == null) 146 {147 header = new Node(element, null , null); 148 // There is only one node. Header and tail point to this node. 154 Node newNode = newNode (Element, tail, null); 156 tail.next = newNode; 158 tail = newNode; 158 tail = newNode; 159 } 160 size++; 161} 162 // Add new nodes to the list using the header method. 163 public void addAtHeader(T element) 164 {162 167 Header = new Node(Element, null, header); 167 Header = new Node(element, null, header); 169 if (tail == null) 170 {171 tail = header; 172 } 173 size++; 174} 175 / / remove linear chain the element at the specified index in the table of 176 public T delete (int index) 177 178 if {(index < 0 | | index > size - 1), 179 {180 throw New IndexOutOfBoundsException (linear table index "cross-border"); 181 } 182 Node del = null; 184 if (index == 0) 185 {186 del = header; 187 header = header.next; 189 header.prev = null; Prev = getNodeByIndex(index-1); // getNodeByIndex(index-1); 196 del = prev.next; 197 // Make the next of the deleted node point to the next node of the deleted node. 198 prev.next = del.next; 199 // Make the prev of the next node of the deleted node point to the prev node. 200 if (del.next ! = null) 201 { 202 del.next.prev = prev; // Set the prev and next references of the deleted node to null. 205 del.prev = null; 206 del.next = null; 207 } 208 size--; 209 return del.data; 212 public T remove() 212 {214 return delete(size-1); 217 public Boolean empty() 218 {219 return size == 0; Public void clear() public void clear() public void clear() public void clear() 226 tail = null; 227 size = 0; 228} 229 public String toString() 230 {231 if (empty()) 233 {234 return "[]"; 235 } 236 else 237 { 238 StringBuilder sb = new StringBuilder("["); 239 for (Node current = header ; current != null 240  ; current = current.next ) 241 { 242 sb.append(current.data.toString() + ", "); 243 } 244 int len = sb.length(); 245 return sb.delete(len - 2 , len).append("]").toString(); 246} 247} 248 Public String reverseToString() 249 {259 if (empty()) 252 {253 return "[]"; 254 } 255 else 256 { 257 StringBuilder sb = new StringBuilder("["); 258 for (Node current = tail ; current != null 259 ;  current = current.prev ) 260 { 261 sb.append(current.data.toString() + ", "); 262 } 263 int len = sb.length(); 264 return sb.delete(len - 2 , len).append("]").toString(); 265} 266} 267}Copy the code

Comparison of two implementations of linear tables \

    • Space performance:
    • Sequential tables: The storage space of a sequential table is statically distributed, requiring an array of fixed length, so some array elements are always wasted.

 

    • Linked lists: Storage space for linked lists is dynamically distributed, so no space is wasted. But because linked lists require extra space to hold Pointers for each node, some space is sacrificed.
    • Time performance:
    • Sequential table: The logical order of elements in a sequential table is consistent with the physical storage order, and random access is supported. So the sequential table in the search, read performance is very good.

 

    • Linked list: Linked lists use a chain structure to store the elements in the list, so it is better for inserting and deleting elements