It introduces the difference between arrays and linked lists, the difference between ArrayList and LinkedList, and the use of LinkedList to simulate stacks and queues.

1 The structure of arrays and linked lists

Similarities:

Arrays and linked lists are linear lists, where arrays are sequential storage implementations, logical storage is the same as physical storage and linked lists are chained storage implementations, logical storage is different from physical storage. Both structures implement logical sequential storage in data structures.

Difference:

  1. Array:
    1. In memory is a contiguous set of memory cells. High memory space requirements, must have enough contiguous memory space.
    2. Each element has its own subscript index, the element can be repeated, each element can be accessed through the subscript index.
    3. Disadvantages: Before storage, we need to apply a contiguous memory space, and must determine its size at compile time. During operation, the size of the space can not be increased or decreased as you need to change, when the amount of data is large, it may be out of bounds, and when the data is small, it may waste memory space.
    4. Array query: The pointer moves up from the initial index until the corresponding data is queried. Fast speed, support random access.
    5. Add and delete: After an element is added or removed from a location, the subscript index is reassigned to the following elements, which is relatively slow (but acceptable).
  2. List:
    1. The distribution of nodes in memory is discontinuous, random and discrete. Nodes are linked by saving a reference to the last \ next node. High memory utilization, no memory waste. Linked list is a dynamic memory application space, do not need to be like the array needs to apply for a good memory size in advance, linked list can only be used when the application, so there is no capacity!
    2. Each element has its own subscript index, the elements can be repeated, and each element can be accessed through the subscript index. But it’s different from the bottom of the array.
    3. Linked list query: as fast as the array, does not support random access, only sequential access;
    4. Add and delete: Directly operate the reference of two adjacent nodes, without moving the latter half of the data as a whole, which is fast.

2 Similarities and differences between ArrayList and LinkedList

Similarities:

  1. Both are non-thread-safe and can only be used under a single thread. In order to prevent asynchronous access, can adopt the following methods to create a List List = Collections. SynchronizedList List (List);
  2. Both LinkedList and ArrayList elements can be null, and the elements are ordered (stored in order).

Difference:

  1. AbstractList; AbstractSequentialList; AbstractSequentialList; AbstractList supports fast random access, that is, looking up collection elements directly through the index; AbstractSequentialList does not support fast random access, only check whether index < (size >> 1) is closer to the top or bottom of the list. Query ArrayList is fast, LinkedList is slow!
  2. Insert, delete elements: The deletion and addition method of LinkedList is basically the reference setting of the previous node and the next node of the node, and does not need to operate other nodes. Compared with ArrayList, the efficiency is very high, because the addition and operation of ArrayList requires traversing and copying the data in the array. And you need to adjust the position of all the numbers after the operation index.
  3. LinkedList does not implement its own Iterator (its Iterator method is called listIterator), but listIterator and DescendingIterator (which implements Iterator);
  4. LinkedList requires more memory because the location of each index in an ArrayList is the actual data, whereas each node in the LinkedList stores the actual data and the location of the surrounding nodes;
  5. The space waste of ArrayList is mainly reflected in reserving a certain amount of space at the end of list, while the space cost of LinkedList is reflected in that each element of it needs to consume a certain amount of space

Application:

  1. Application scenarios of ArrayLsit: frequent query operations but few add and delete operations.
  2. Application scenario of LinkedList: Less query operations, frequent add and delete operations.

Stack and queue simulation

Stack features: FILO first after out

The characteristics of the queue: FIFO first in first out

Emulated queues and stacks with LinkedList: (Decorator design pattern)

  1. Create a class: MyQueue or MyStack
  2. Introduce the LinkedList class, defined as a global variable.
  3. Provides a constructor for the class that initializes global variables.
  4. Provides methods for storing and fetching, as well as methods for determining whether null is present.

3.1 simulation stack

/** * LinkedList emulated stack *@author lx
 */
public class MyStackFromLinkedList<T> {
    private LinkedList<T> ll;

    public MyStackFromLinkedList(a) {
        this.ll = new LinkedList<>();
    }

    /** * push *@paramObj pushes the element */
    public void add(T obj) {
        ll.offerFirst(obj);
    }

    /** * out of the stack *@returnOut of the stack element */
    public T get(a) {
        return ll.pollFirst();
    }

    /** * whether the stack is empty *@returnTrue - empty; False - not empty * /
    public Boolean isEmpty(a) {
        returnll.isEmpty(); }}/**
 * 测试
 */
class MyStackTest {
    public static void main(String[] args) {
        MyStackFromLinkedList<String> myStack = new MyStackFromLinkedList<>();
        / / into the stack
        myStack.add("aa");
        myStack.add("bb");
        myStack.add("cc");
        myStack.add("dd");
        while(! myStack.isEmpty()) {// unstack
            Object o = myStack.get();
            //dd cc bb aa
            System.out.print(o + ""); }}}Copy the code

3.2 Simulated Queue

/** * LinkedList emulated queue *@author lx
 */
public class MyQueueFromLinkedList<T> {
    private LinkedList<T> ll;

    public MyQueueFromLinkedList(a) {
        this.ll = new LinkedList<>();
    }

    /** * queue **@paramObj joins the team */
    public void add(T obj) {
        ll.offerFirst(obj);
    }

    /** ** exit queue **@returnTeam out elements */
    public T get(a) {
        return ll.pollLast();
    }

    public Boolean isEmpty(a) {
        returnll.isEmpty(); }}/**
 * 测试
 */
class MyQueueTest {
    public static void main(String[] args) {
        MyQueueFromLinkedList<String> myQueue = new MyQueueFromLinkedList<>();
        / / into the queue
        myQueue.add("a");
        myQueue.add("b");
        myQueue.add("c");
        myQueue.add("d");
        while(! myQueue.isEmpty()) {// The first to queue is the first to queue
            Object o = myQueue.get();
            //a b c d
            System.out.print(o + ""); }}}Copy the code

If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!