Technology Sharing

[Java Data Structure] Introduction to Linear List 1: Sequential List

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Using Java to simply implement a sequence table

A sequential list is a linear structure that uses a continuous physical address storage unit to store data elements in sequence. Generally, it uses an array to store data. Add, delete, query, and modify data on the array.

Linear tables generally include the following methods:

public class MyArrayList {
    private int[] array;
    private int size;
   // The default constructor allocates space by default
    SeqList(){   }
    // Set the underlying capacity of the sequence table to the specified capacity
    SeqList(int initcapacity){   }

   // Add new elements, added at the end of the array by default
    public void add(int data) { }
    // Add an element at position pos
    public void add(int pos, int data) { }
   // Determine whether an element is contained
    public boolean contains(int toFind) { return true; }
    // Find the position corresponding to an element
    public int indexOf(int toFind) { return -1; }
    // Get the element at position pos
    public int get(int pos) { return -1; }
   // Set the element at position pos to value
    public void set(int pos, int value) {   }
    //Delete the first occurrence of the keyword key
    public void remove(int toRemove) {   }
   // Get the length of the sequence table
    public int size() { return 0; }
    // Clear the sequence table
    public void clear() {   }
   
   // Print order table
    public void display() {   }
}

Next, implement a sequence table of int type according to the above method:

  1. import java.util.Arrays;
  2. public class MyArrayList {
  3.     private int[] elem;
  4.     private int usedSize;
  5.     private static final int DEFAULT_SIZE = 10;
  6.     public MyArrayList(){
  7.         elem = new int[DEFAULT_SIZE];
  8.     }
  9.     public MyArrayList(int initCapacity){
  10.         elem = new int[initCapacity];
  11.     }
  12.  
  13.     private boolean checkCapacity(){
  14.         if(this.usedSize == elem.length){
  15.             return true;
  16.         }
  17.         return false;
  18.     }
  19.  
  20.     public void display(){
  21.         for (int i = 0; i < this.usedSize; i++) {
  22.             System.out.print(this.elem[i] + " ");
  23.         }
  24.     }
  25.     public void add(int data){
  26.         if(checkCapacity()){
  27.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
  28.         }
  29.         this.elem[this.usedSize] = data;
  30.         this.usedSize++;
  31.         return;
  32.     }
  33.     public void add(int pos,int data){
  34.         if(pos > this.usedSize || pos < 0){
  35.             throw new PosOutOfBoundsException("插入位置错误！");
  36.         }
  37.         if(checkCapacity()){
  38.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
  39.         }
  40.         for (int i = this.usedSize - 1; i >=pos ; i--) {
  41.             elem[i+1] = elem[i];
  42.         }
  43.         this.elem[pos] = data;
  44.         this.usedSize++;
  45.         return;
  46.     }
  47.  
  48.     public boolean contains(int data){
  49.         for (int i = 0; i < this.usedSize; i++) {
  50.             if(this.elem[i] == data){
  51.                 return true;
  52.             }
  53.         }
  54.         return false;
  55.     }
  56.  
  57.     public int indexof(int data){
  58.         for (int i = 0; i < this.usedSize; i++) {
  59.             if(this.elem[i] == data){
  60.                 return i;
  61.             }
  62.         }
  63.         return -1;
  64.     }
  65.     public int get(int pos){
  66.         if(pos >= this.usedSize || pos < 0){
  67.             throw new PosOutOfBoundsException("输入的位置错误！");
  68.         }
  69.         return this.elem[pos];
  70.     }
  71.     public void set(int pos,int data){
  72.         if(pos >= this.usedSize || pos < 0){
  73.             throw new PosOutOfBoundsException("输入的位置错误！");
  74.         }
  75.         this.elem[pos] = data;
  76.     }
  77.     public int size(){
  78.         return this.usedSize;
  79.     }
  80.     public void remove(int data){
  81.         if(this.contains(data)){
  82.             int pos = this.indexof(data);
  83.             for (int i = pos; i < this.usedSize - 1; i++) {
  84.                 this.elem[pos] = this.elem[pos+1];
  85.             }
  86.             this.usedSize--;
  87.         }else{
  88.             throw new PosOutOfBoundsException("没有该元素");
  89.         }
  90.     }
  91.     public void clear(){
  92.         this.usedSize = 0;
  93.         return;
  94.     }
  95. }

Introduction to ArrayList

In the collection framework, ArrayList is a common class that implements the List interface. The specific framework diagram is as follows:

  • ArrayList is implemented in a generic way and must be instantiated before use.
  • ArrayList implements the RandomAccess interface, indicating that ArrayList supports random access
  • ArrayList implements the Cloneable interface, indicating that ArrayList can be cloned
  • ArrayList implements the Serializable interface, indicating that ArrayList supports serialization
  • Unlike Vector, ArrayList is not thread-safe. It can be used in a single thread. In multi-threaded environments, you can choose Vector or
  • CopyOnWriteArrayList
  • The underlying space of ArrayList is a continuous space, which can be expanded dynamically. It is a dynamic type of sequential list.

How to use ArrayList

ArrayList Constructor

Constructor in ArrayList:

ArrayList(); //Construction without parameters

ArrayList(Collection<? extends E> c); //Use other Collections to build ArrayList

ArrayList(int initialCapacity); //Specify the initial capacity of the sequence list

Code example:

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list1 = new ArrayList<>();//无参构造
  4.         List<Integer> list2 = new ArrayList<>(10);//指定容量
  5.         list2.add(1);
  6.         list2.add(2);
  7.         list2.add(3);
  8.         List<Integer> list3 = new ArrayList<>(list2);//利用其他 Collection 构建 ArrayList
  9.     }
  10. }

ArrayList Common Operations

Tail plug

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();//无参构造
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list);
  8.     }
  9. }

Inserts an element at the specified position

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.add(1,4);
  8.         System.out.println(list);
  9.     }
  10. }

Insert the element in another sequence at the end

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer>  list1 = new ArrayList<>();
  4.         list1.add(4);
  5.         list1.add(5);
  6.         list1.add(6);
  7.         List<Integer> list = new ArrayList<>();
  8.         list.add(1);
  9.         list.add(2);
  10.         list.add(3);
  11.         list.addAll(list1);
  12.         System.out.println(list);
  13.     }
  14. }

Delete the element at the specified position

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.remove(1);
  8.         System.out.println(list);
  9.     }
  10. }

Delete specified data

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.remove(new Integer(2));
  8.         System.out.println(list);
  9.     }
  10. }

Get the element at the specified position

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list.get(1));
  8.     }
  9. }

Set the element at the specified position to the new data

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.set(1,4);
  8.         System.out.println(list);
  9.     }
  10. }

Clear sequence table

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.clear();
  8.         System.out.println(list);
  9.     }
  10. }

Determine whether an element is in the sequence list

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list.contains(2));
  8.         System.out.println(list.contains(4));
  9.     }
  10. }

Returns the index of the first specified element

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.add(1);
  8.         System.out.println(list.indexOf(1));
  9.     }
  10. }

Returns the index of the last specified element

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.add(1);
  8.         System.out.println(list.lastIndexOf(1));
  9.     }
  10. }

Extract part of the list

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list.subList(0,2));
  8.     }
  9. }

Three ways to traverse an ArrayList

ArrayList can be traversed in three ways: for loop + subscript, foreach enhanced loop, and using iterators

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         //使用fori遍历
  8.         for (int i = 0; i < list.size(); i++) {
  9.             System.out.print(list.get(i));
  10.         }
  11.         System.out.println();
  12.         //使用foreach遍历
  13.         for(Integer integer:list){
  14.             System.out.print(integer);
  15.         }
  16.         System.out.println();
  17.         //使用迭代器遍历
  18.         Iterator<Integer> it = list.listIterator();
  19.         while(it.hasNext()){
  20.             System.out.print(it.next());
  21.         }
  22.     }
  23. }

operation result:

ArrayList usage scenarios

Shuffling Algorithm

A deck of playing cards is randomly shuffled and distributed to three people, with five cards each.

The original code of the algorithm is located at:

shufflecards · A freshwater fish/Java classic example - Code Cloud - Open Source China (gitee.com)

Pascal's Triangle

Description of the topic:

Code:

  1. public class Test {
  2.     public static List<List<Integer>> generate(int numRows) {
  3.         List<List<Integer>> list = new LinkedList<>();
  4.         for (int i = 0; i < numRows; i++) {
  5.             List<Integer> row = new LinkedList<>();
  6.             for (int j = 0; j < i + 1; j++) {
  7.                 if (j == 0 || i == j) {
  8.                     row.add(1);
  9.                 } else {
  10.                     row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
  11.                 }
  12.             }
  13.             list.add(row);
  14.         }
  15.         return list;
  16.     }
  17.  
  18.     public static void main(String[] args) {
  19.         Scanner scanner = new Scanner(System.in);
  20.         int numRows = scanner.nextInt();
  21.         List<List<Integer>> list = generate(numRows);
  22.         for (int i = 0; i < numRows; i++) {
  23.             for (int j = 0; j < i + 1; j++) {
  24.                 System.out.print(list.get(i).get(j) + " ");
  25.             }
  26.             System.out.println();
  27.         }
  28.     }
  29. }

Running result chart:

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail