catalogue
🎶 Gets the effective length of the sequence table
🎶 Determine whether an element
🎶 Find the corresponding position of an element. If it is not found, return - 1
🎶 Gets the element of the pos location
🎶 Set / update the element of pos position to value
🎶 Delete the keyword key that appears for the first time
🎶 Concept and structure of linked list
🎶 Implementation of linked list
🎶 Find out whether the keyword is included and whether the key is in the single linked list
🎶 Get the length of the single linked list
🎶 Find the address of the node at index-1
🎶 Find the precursor of the keyword to delete
🎶 Delete the node whose keyword is key for the first time
🎶 Delete all nodes with the value of key
🙌 Write in front
Linear list and linked list are the most important in learning. It can be placed in the front of data structure, which shows its importance. The most important thing to learn data structure well is to draw pictures and write more code. Some fixed structures are fixed syntax. Who can be skillful when you know more. If you think this article is well written, please praise, collect and comment. Your third company is my greatest progress in learning. Don't talk more nonsense. Let's learn it!
🙌 Linear table
A linear list is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables include sequential table, linked list, stack, queue and string
A linear table is logically a linear structure, that is, a continuous straight line. However, the physical structure is not necessarily continuous. When the linear table is stored physically, it is usually stored in the form of array and chain structure.
🙌 Sequence table
🎶 Concept and structure
Sequential table is a linear structure in which data elements are stored in sequence with a storage unit with continuous physical addresses. Generally, array storage is used. Complete the addition, deletion, query and modification of data on the array.
The sequence table can generally be divided into:
Static sequential table: use fixed length array storage.
Dynamic sequential table: use dynamic array storage.
The static sequence table is suitable for scenarios where you know how much data needs to be stored
The fixed length array of static sequence table leads to large N, waste of space and insufficient space
In contrast, the dynamic sequential table is more flexible and dynamically allocates space according to needs.
🎶 Interface implementation
class SeqList {
// Print sequence table
public void display() {
}
// Add new element in pos position
public void add(int pos, int data) {
}
// Determines whether an element is included
public boolean contains(int toFind) {
return true;
}
// Find the location of an element
public int search(int toFind) {
return -1;
}
// Gets the element of the pos location
public int getPos(int pos) {
return -1;
}
// Set the element of pos position to value
public void setPos(int pos, int value) {
}
//Delete the keyword key that appears for the first time
public void remove(int toRemove) {
}
// Get sequence table length
public int size() {
return 0;
}
// Empty sequence table
public void clear() {
}
}🎶 Create sequence table
public int[] elem;
public int usedSize;//Number of valid data
public MyArrayList() {
this.elem = new int[10];
}🎶 Print sequence table
// Print sequence table
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}🎶 Gets the effective length of the sequence table
// Gets the valid data length of the sequence table
public int size() {
return this.usedSize;
}
🎶 Add element in pos position
public boolean isFull() {
return this.usedSize == this.elem.length;
} // Add new element in pos position
public void add(int pos, int data) {
if(pos < 0 || pos > usedSize) {
System.out.println("pos Illegal location!");
return;
}
if(isFull()) {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3,
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0,1);
myArrayList.add(1,2);
myArrayList.add(2,3);
myArrayList.add(3,4);
myArrayList.display();
}
🎶 Determine whether an element
// Determines whether an element is included
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return true;
}
}
return false;
}🎶 Find the corresponding position of an element. If it is not found, return - 1
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return i;
}
}
return -1;
}🎶 Gets the element of the pos location
public int getPos(int pos) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos Illegal location");
return -1;//So let's explain here that exceptions can be thrown in the later stage of business processing
}
if(isEmpty()) {
System.out.println("Sequence table is empty!");
return -1;
}
return this.elem[pos];
}public boolean isEmpty() {
return this.usedSize==0;
}🎶 Set / update the element of pos position to value
public void setPos(int pos, int value) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos Illegal location");
return;
}
if(isEmpty()) {
System.out.println("Sequence table is empty!");
return;
}
this.elem[pos] = value;
}🎶 Delete the keyword key that appears for the first time
public void remove(int toRemove) {
if(isEmpty()) {
System.out.println("Sequence table is empty!");
return;
}
int index = search(toRemove);
if(index == -1) {
System.out.println("There are no numbers you want to delete!");
return;
}
for (int i = index; i < this.usedSize-1; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize] = null; If there is a reference data type in the array.
}public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0,1);
myArrayList.add(1,2);
myArrayList.add(2,3);
myArrayList.add(3,4);
myArrayList.remove(3);
myArrayList.display();
}
✨ Complete code ✨
❤️Textdemo.java
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0, 1);
myArrayList.add(1, 2);
myArrayList.add(2, 3);
myArrayList.add(3, 4);
myArrayList.display();
myArrayList.remove(29);
System.out.println("==============");
myArrayList.clear();
myArrayList.display();
System.out.println(myArrayList.contains(3));
System.out.println(myArrayList.getPos(21));
}❤️MyArrayLinst.java
import java.util.ArrayList;
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* User: 12629
* Date: 2021/10/31
* Time: 10:28
* Description:Sequence table
*/
public class MyArrayList {
public int[] elem;
public int usedSize;//Number of valid data
public MyArrayList() {
this.elem = new int[10];
}
// Print sequence table
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
// Gets the valid data length of the sequence table
public int size() {
return this.usedSize;
}
// Add new element in pos position
public void add(int pos, int data) {
if(pos < 0 || pos > usedSize) {
System.out.println("pos Illegal location!");
return;
}
if(isFull()) {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3,
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
// Determines whether an element is included
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return true;
}
}
return false;
}
// Find the corresponding position of an element. If it is not found, return - 1
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return i;
}
}
return -1;
}
// Gets the element of the pos location
public int getPos(int pos) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos Illegal location");
return -1;//So let's explain here that exceptions can be thrown in the later stage of business processing
}
if(isEmpty()) {
System.out.println("Sequence table is empty!");
return -1;
}
return this.elem[pos];
}
public boolean isEmpty() {
return this.usedSize==0;
}
// Set / update the element of pos position to value
public void setPos(int pos, int value) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos Illegal location");
return;
}
if(isEmpty()) {
System.out.println("Sequence table is empty!");
return;
}
this.elem[pos] = value;
}
//Delete the keyword key that appears for the first time
public void remove(int toRemove) {
if(isEmpty()) {
System.out.println("Sequence table is empty!");
return;
}
int index = search(toRemove);
if(index == -1) {
System.out.println("There are no numbers you want to delete!");
return;
}
for (int i = index; i < this.usedSize-1; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize] = null; If there is a reference data type in the array.
}
// Empty sequence table
public void clear() {
this.usedSize = 0;
/*for (int i = 0; i < usedSize; i++) {
this.elem[i] = null;
}
this.usedSize = 0;
*/
}
}
🙌 Linked list
🎶 Concept and structure of linked list
Linked list is a discontinuous storage structure in physical storage structure. The logical order of data elements is realized through the reference link order in the linked list.
🎶 Linked list classification
🎶 Implementation of linked list
// 1. Implementation of headless one-way acyclic linked list
public class SingleLinkedList {
//Head insertion
}
public void addFirst(int data){
//Tail interpolation
}
public void addLast(int data){
//Insert at any position, and the first data node is subscript 0
}
public boolean addIndex(int index,int data){
//Find out whether the keyword is included and whether the key is in the single linked list
}
public boolean contains(int key){
//Delete the node whose keyword is key for the first time
}
public void remove(int key){
//Delete all nodes with the value of key
}
public void removeAllKey(int key){
//Get the length of the single linked list
}
public int size(){
}
public void display(){
}
public void clear(){
}
}
🎶 Create node
public ListNode head;//Header reference of linked list
lass ListNode {
public int val;
public ListNode next;//null
public ListNode(int val) {
this.val = val;
}
🎶 Create linked list
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
//listNode5.next = null;
this.head = listNode1;
}🎶 Print linked list
public void display() {
//this.head.next != null
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
} public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
myLinkedList.display();
}
🎶 Find out whether the keyword is included and whether the key is in the single linked list
public boolean contains(int key){
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
myLinkedList.display();
boolean flg = myLinkedList.contains(56);
}🎶 Get the length of the single linked list
public int size(){
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
System.out.println(myLinkedList.size());
}
🎶 Head insertion
//Head insertion
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
/*if(this.head == null) {
this.head = node;
}else {
node.next = this.head;
this.head = node;
}*/
} public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
myLinkedList.addFirst(10);
myLinkedList.display();
}
🎶 Tail interpolation
//Tail interpolation
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
}else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
//cur.next == null;
cur.next = node;
}
} public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
myLinkedList.addLast(90);
myLinkedList.display();
}
🎶 Find the address of the node at index-1
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index-1 != 0) {
cur = cur.next;
index--;
}
return cur;
}🎶 Insert element
//Insert at any position, and the first data node is subscript 0
public void addIndex(int index,int data){
if(index < 0 || index > size()) {
System.out.println("index Illegal location!");
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
myLinkedList.addLast(90);
myLinkedList.addIndex(2,20);
myLinkedList.display();
}
🎶 Find the precursor of the keyword to delete
public ListNode searchPerv(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if(cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}🎶 Delete the node whose keyword is key for the first time
//Delete the node whose keyword is key for the first time
public void remove(int key){
if(this.head == null) {
System.out.println("The single linked list is empty and cannot be deleted!");
return;
}
if(this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPerv(key);
if(cur == null) {
System.out.println("There is no node you want to delete!");
return;
}
ListNode del = cur.next;
cur.next = del.next;
} public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
myLinkedList.addLast(90);
myLinkedList.remove(23);
myLinkedList.display();
}
🎶 Delete all nodes with the value of key
//Delete all nodes with the value of key
public ListNode removeAllKey(int key){
if(this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//Final processing head
if(this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(23);
myLinkedList.addLast(23);
myLinkedList.addLast(56);
myLinkedList.addLast(90);
myLinkedList.removeAllKey(23);
myLinkedList.display();
}
🎶 Empty linked list
public void clear(){
//this.head == null
while (this.head != null) {
ListNode curNext = head.next;
this.head.next = null;
this.head = curNext;
}
}✨ All codes ✨
❤️TextDemo.java
class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(23);
myLinkedList.addLast(23);
myLinkedList.addLast(56);
myLinkedList.addLast(90);
myLinkedList.display();
}
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
//myLinkedList.createList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(45);
myLinkedList.addFirst(156);
myLinkedList.addIndex(31,99);
myLinkedList.display();
boolean flg = myLinkedList.contains(56);
}
}❤️MyLinlLinst.java
**
* Created with IntelliJ IDEA.
* User: 12629
* Date: 2021/11/2
* Time: 19:00
* Description:
*/
//ListNode represents a node
class ListNode {
public int val;
public ListNode next;//null
public ListNode(int val) {
this.val = val;
}
}
public class MyLinkedList {
public ListNode head;//Header reference of linked list
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
//listNode5.next = null;
this.head = listNode1;
}
public void display() {
//this.head.next != null
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//Find out whether the keyword is included and whether the key is in the single linked list
public boolean contains(int key){
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//Get the length of the single linked list
public int size(){
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//Head insertion
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
/*if(this.head == null) {
this.head = node;
}else {
node.next = this.head;
this.head = node;
}*/
}
//Tail interpolation
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
}else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
//cur.next == null;
cur.next = node;
}
}
/**
* Find the address of the node at index-1
* @param index
* @return
*/
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index-1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//Insert at any position, and the first data node is subscript 0
public void addIndex(int index,int data){
if(index < 0 || index > size()) {
System.out.println("index Illegal location!");
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
/**
* Find the precursor of the keyword to delete
* @param key
* @return
*/
public ListNode searchPerv(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if(cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//Delete the node whose keyword is key for the first time
public void remove(int key){
if(this.head == null) {
System.out.println("The single linked list is empty and cannot be deleted!");
return;
}
if(this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPerv(key);
if(cur == null) {
System.out.println("There is no node you want to delete!");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
//Delete all nodes with the value of key
public ListNode removeAllKey(int key){
if(this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//Final processing head
if(this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}
public void clear(){
//this.head == null
while (this.head != null) {
ListNode curNext = head.next;
this.head.next = null;
this.head = curNext;
}
}
}