How to implement a custom LinkedList class in Java

1. LinkedList and ArrayList

--	LinkedList	ArrayList
Contact	They are all implementation classes of List, all under the java.util package
Implementation principle	Operation data through linked lists	Manipulate data through arrays
When to use	Change and check	Add and delete

2. Customize the LinkedList class (one-way linked list)

1. Implementation ideas

The LinkedList class is different from the ArrayList class. It adds, deletes, modifies and checks the linked list through the operation of pointers and nodes

Steps to customize the LinkedList class

1. Create a node class whose attributes are node nodes of Node type and data of Object type

2. Create a node class Parameterized and parameterless construction methods

3. Create your own LinkedList class to implement the List interface

4. Create a new node object in the LinkedList class and declare a size to represent the collection. Element

5. Implement the methods of size(), get(), and isEmpty() (similar to ArrayList)

6. Write an add() method with formal parameters

7. Write the add() method with two formal parameters

8. Create a test class to test the code

2. Node node class

There are two Attributes: Node and data

The type of the node is Node

The type of the data is Object (because it is not possible to determine the specific type of the incoming data)

package MyLinkedList;

public class Node {
    // 定义数据
    Object data;
    // 定义下一结点
    Node next;

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Node() {
    }
}

3. size(), isEmpty(), get(int index)

size() method

@Override
    public int size() {
        return size;
    }

isEmpty() method

 @Override
    public boolean isEmpty() {
        return size == 0;
    }

get(int index) method

 @Override
    public Object get(int index) {
        Node p = node;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }

        return p.data;
    }

4, add(Object o)

Insert the received data at the end

@Override
    public boolean add(Object o) {
        add(size, o);
        return true;
    }

5, add(int index,Object element)

 @Override
    public void add(int index, Object element) {
        // 找到需要插入的位置的结点
        Node p = node;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        // 创建新结点
        Node node1 = new Node();

        // 将数据存入集合中
        node1.data = element;

        // 让node1的指针指向下一结点
        node1.next = p.next;

        // 确定node1的直接前驱结点
        p.next = node1;

        // 更新size
        size++;
    }

6, test class

The reason why the loop starts from 1: because an object is created at the beginning in the LinkedList class , if you start from 0, you will see that the printed result is null

package MyLinkedList;

public class test {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add("111");
        linkedList.add("222");
        linkedList.add("333");
        linkedList.add("444");
        for (int i = 1; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
        System.out.println("==================");
        linkedList.add(2,999);
        for (int i = 1; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }

    }
}

The above is the detailed content of How to implement a custom LinkedList class in Java. For more information, please follow other related articles on the PHP Chinese website!