Introduction to the

Linear list is divided into: sequential list, linked list, stack and queue structure: sequential storage structure & chain storage structure

Sequential table & sequential storage structure

Implementation: array

Features:

  1. The way to store the data elements of a linear table = a sequence of contiguous addresses
  2. Have: start position, array length (maximum storage capacity) & linear table length (current length)

Operations: Operations on sequential storage structures include insert and delete

Chain storage structure

Implementation: linked list features: chained storage structure of data elements = a segment of address discontinuous storage units: single linked list, bidirectional linked list, circular linked list, static linked list

Singly linked lists

Features: chained access data structure, single linked list data in the form of nodes, each node is composed of data elements and the storage location of the next node. Each node has only one pointer domain node

Public class UnidirectionalLinkedList<T> {/** * set node structure */ / Private class Node<T>{private T data; private Node<T> next ; public Node(T data){ this.data = data; }} // b. Private Node<T> first; // c. Private Node<T> currentNode; // d. Private int size; Public UnidirectionalLinkedList(){currentNode = first = null; size = 0; } /** * 1. Add nodes * content: add nodes at the beginning/end & insert nodes at specific locations */ / a. Public void addFirstNode(T data){// 1. NewNode = newNode <T>(data); Newnode. next = first; // next = first; // set first = newNode; // 4. List length +1 size++; Public void addNode(T data){// 1. If (isEmpty()){addFirstNode(data); return; } // 2. Locate the current pointer to the last node locateNode(sie-1); Currentnode. next = new Node<T>(data); // 4. List length +1 size++; } public T insertNode(int index, T data) {// 1. If (isEmpty()){addFirstNode(data); return null; } // 2. Insert the current pointer to the node locateNode(index); Node<T> insertNode = new Node<T>(data); Insertnode. next = currentNode.next; CurrentNode. Next = insertNode; // 6. List length +1 size++; // 7. Return insertNode.data; } /** * 2. Delete node * content: delete first node & delete node */ / Public T removeFirstNode() {// 1. If (first == null){try {throw new Exception(" List is empty!" ); } catch (Exception e) { e.printStackTrace(); T temp = first.data; First = first.next; // 4. List length minus 1 size--; // 5. Return temp; } public T removeNode(int index) {// 1. If (isEmpty()){try {throw new Exception(" the list isEmpty!" ); } catch (Exception e) { e.printStackTrace(); }} // 2. Locate the current pointer (currentNode) to the first node (index) locateNode(index-1); T temp = currentNode.next. Data; Currentnode.next = currentNode.next-next; currentNode.next = currentNode.next-next; currentNode.next-next = currentNode.next-next; // 5. List length minus 1 size--; // 6. Return temp; } /** * 1;} /** * 2; Private void locateNode(int index){// 1. To determine whether a pointer across the if (index < 0 && index > size) {try {throw new IndexOutOfBoundsException (" parameter bounds!" ); } catch (Exception e) { e.printStackTrace(); } } int i = 0; For (currentNode = first; currentNode.next ! = null && i < index; i++){ currentNode = currentNode.next; Public T getNode(int index) {// 1. If (isEmpty()){try {throw new Exception(" the list isEmpty!" ); } catch (Exception e) { e.printStackTrace(); }} // 2. Insert currentNode into index (index) locateNode(index); // 3. Return currentNode.data; } /** * Public Boolean isEmpty(){if (size == 0){return true; }else { return false; } } public static void main(String[] args){ // 1. UnidirectionalLinkedList<Integer> list = new UnidirectionalLinkedList<Integer>(); list.addNode(1); list.addNode(2); list.addNode(3); list.addNode(4); list.addNode(5); // 2. Output the current list data system.out.println (" List data is as follows: "); for (int i = 0; i < list.size; i++){ try { System.out.print(list.getNode(i)+" "); } catch (Exception e) { e.printStackTrace(); } } System.out.println("-----------------------"); System.out.println(" + list.getNode(3)); System.out.println("-----------------------"); System.out.println(" data inserted at 4: "+ list.insertnode (3,66)); System.out.println(" insert after: "); for (int i = 0; i < list.size; i++){ try { System.out.print(list.getNode(i)+" "); } catch (Exception e) { e.printStackTrace(); } } System.out.println("-----------------------"); Println (" delete data with index 3: "+ list.removenode (3)); System.out.println(" delete: "); for (int i = 0; i < list.size; i++){ try { System.out.print(list.getNode(i)+" "); } catch (Exception e) { e.printStackTrace(); }}}}Copy the code

Circular list,

The pointer of the end node of the single linked list points to the head node, so that the head and tail of the single linked list are connected to form a ring

Two-way linked list

Features: Each node has two pointer fields: 1 points to the rear drive node element, 2 points to the front drive node element

package com.struct.linklist; Linklist * @class name linkList * @author chenlin * @date June 26, 2010 @version 1.0 */ public class DoubleLinkList {// header private Node first; // private Node last; public DoubleLinkList(){ first = null; last = null; } /** * public void insertFirst(long value){Node newNode = newNode (value); if (first == null) { last = newNode; }else { first.previous = newNode; // Move first down newNode.next = first; } first = newNode; } @param value */ public void insertLast(long value){Node newNode = newNode (value); if (first == null) { first = newNode; }else { last.next = newNode; //first.previous = newNode; newNode.previous = last; } // Set the last node to the latest node. } public boolean isEmpty(){ return first == null; } @param value @return */ public Node deleteFirst(){if (){if (){}} @param value @return */ public Node deleteFirst(){if () (first == null) {throw new RuntimeException(" List data does not exist "); } Node temp = first; if (first.next == null) { last = null; }else { first.next.previous = null; } first = temp.next; return temp; } @param value @return */ public Node deleteLast(){if ** ** public Node deleteLast(){if ** ** public Node deleteLast(){if (first == null) {throw new RuntimeException(" List data does not exist "); } Node temp = last; if (first.next == null) { last = null; First = null; }else { last.previous.next = null; } last = temp.previous; return temp; } /** * delete @param key * @return */ public Node deleteByKey(long key){Node current = first; while(current.data ! = key){if (current. Next == null) {system.out.println (" not found "); return null; } current = current.next; } if (current == first) { //return deleteFirst(); First = first.next; }else { current.previous.next = current.next; } return current; Public void display(){if (first == null) {//throw new RuntimeException(" List data does not exist "); return; } Node current = first; while(current ! = null){ current.display(); current = current.next; } System.out.println("---------------"); } public Node findByValue(long value){Node current = first; while(current ! = null){ if (current.data ! = value) { current = current.next; }else { break; }} if (current == null) {system.out.println (" not found "); return null; } return current; } public Node findByKey(long key) {Node current = first; while (current.data ! = key) {if (current. Next == null) {system.out.println (" not found "); return null; } current = current.next; } return current; } @param position * @return */ public Node findByPosition(int position){Node current = first; For (int I = 0; int I = 0; int I = 0; i < position - 1 ; i++) { current = current.next; } return current; } public static void main(String[] args) { DoubleLinkList linkList = new DoubleLinkList(); linkList.insertFirst(21); linkList.insertFirst(22); linkList.insertFirst(23); linkList.insertLast(24); linkList.insertLast(25); linkList.insertLast(26); linkList.insertLast(27); linkList.display(); System. The out. Println (" -- -- -- for -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "); linkList.findByKey(25).display(); System. The out. Println (" -- -- delete the first -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "); //linkList.deleteFirst().display(); ///linkList.deleteFirst().display(); //linkList.deleteFirst().display(); //linkList.deleteFirst().display(); System. The out. Println (" - delete specified value -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "); linkList.deleteByKey(27).display(); linkList.deleteByKey(21).display(); System.out.println("----------------------------------------"); linkList.display(); }}Copy the code

A static linked list

A list described by an array is called a static list. Features: This storage structure still needs to allocate a large space in advance, but as a linear table insert and delete operations do not need to move elements, only to modify the pointer, so it still has the main advantages of the chain storage structure.

/** * @description TODO * @date 2019年3月23日 9:08:11 * @author tmooming */ public class SNode<T> {public T data; private int cursor; public SNode() { } public SNode(T data, int cursor) { this.data = data; this.cursor = cursor; } public T getData() { return data; } public void setData(T data) { this.data = data; } public int getCursor() { return cursor; } public void setCursor(int cursor) { this.cursor = cursor; } @Override public String toString() { StringBuffer sb = new StringBuffer(); sb.append(getData()); sb.append(" "); sb.append(getCursor() + " "); return sb.toString(); }} /** * @description TODO * @date * @author tmooming */ public class SNode<T> {SNode<T>[] node; private static final int MAX_SIZE = 15; private int length; public SList() { node = new SNode[MAX_SIZE]; for (int i = 0; i < MAX_SIZE - 1; i++) { node[i] = new SNode<T>(null, i + 1); } node[MAX_SIZE - 1] = new SNode<>(null, 0); this.length = 0; } public int Length() {return Length; } public Boolean isEmpty() {return length == 0; } public Boolean isFull() {return length == MAX_SIZE; } public Boolean addTo(T data, int index) { if (isFull() || index > MAX_SIZE || index < -1 || data == null) return false; if (index == 0) { insert(data); return true; } if (index > Length()) { index = Length(); } int firstUse = node[MAX_SIZE - 1].getCursor(); Int firstNull = node[0].getCursor(); for (int i = 1; i < index; i++) { firstUse = node[firstUse].getCursor(); } int nextUse = node[firstUse].getCursor(); int nextNull = node[firstNull].getCursor(); node[0].setCursor(nextNull); node[firstUse].setCursor(firstNull); node[firstNull].setCursor(nextUse); node[firstNull].setData(data); length++; return true; } public void insert(T data) { int t = node[MAX_SIZE - 1].getCursor(); int firstNull = node[0].getCursor(); node[MAX_SIZE - 1].setCursor(firstNull); node[0].setCursor(node[firstNull].getCursor()); node[firstNull].setCursor(t); node[firstNull].setData(data); length++; } public void print() { int first = node[MAX_SIZE - 1].getCursor(); System.out.println(" list: "); for (int i = first; i ! = 0;) { System.out.print(node[i].getData() + " "); i = node[i].getCursor(); Public Boolean delete(T data) {if (isEmpty()) {return false; } int temp = MAX_SIZE - 1; while (temp ! = 0) { if (node[node[temp].getCursor()].getData() == data) { int p = node[temp].getCursor(); node[temp].setCursor(node[p].getCursor()); node[p].setCursor(node[0].getCursor()); node[0].setCursor(p); node[p].setData(null); length--; return true; } temp = node[temp].getCursor(); } return false; } public Boolean deleteAll() {if (isEmpty()) {return true; } for (int i = 0; i < MAX_SIZE - 1; i++) { node[i].setCursor(i + 1); node[i].setData(null); } node[MAX_SIZE - 1].setCursor(0); node[MAX_SIZE - 1].setData(null); length = 0; return true; } public void printAll() {system.out.println (" list: "); for (int i = 0; i < MAX_SIZE; i++) { System.out.print("[" + i + " " + node[i].getData() + " " + node[i].getCursor() + "]"); if (i % 5 == 0 && i ! = 0) { System.out.println(); } } } public static void main(String[] args) { SList<String> list = new SList<String>(); List. The insert (" z "); List. The insert (" money "); List. The insert (" li "); // list.printAll(); // list.addTo(" sun ", 5); list.deleteAll(); System.out.println(list.Length()); list.printAll(); }}Copy the code