preface

Welcome to our GitHub repository Star: github.com/bin39232820… The best time to plant a tree was ten years ago, followed by now

omg

The foundation of the previous 2, we still have a good study, the following is the link

🔥 Introduction to the most complete Java container collection 🔥 The most complete Java container collection of basic data structures (hand tore list) 🔥 The most complete Java container collection of ArrayList(source code read)

Today we are going to talk about Vector and LinkedList(by the way, if you have no basic knowledge, you are not recommended to come and have half a year of work experience to go through these with me, it will be very helpful).

Vector source code analysis

There is not much more to say about Vector, because it is similar to the code of ArrayList, except that each method is locked, as shown below

Since most of them are pretty much the same, let me talk about the different points

If you look at the top of the graph, this is another point where Vetor differs from ArrayList and the growth factor is self-definable. Let’s look at the grow method

This code is the expansion code, you can see if you define the growth factor each time the expansion factor, otherwise it is 2 times

I won’t say anything about the other additions, deletions, changes and checks, and I haven’t looked at them myself, but the underlying array is the same, so most of them are the same except for a synchronized lock

Just to remind you that an ArrayList can also be made thread safe

If you want a ArrayList synchronization, can use the method of the Collections: List the List = Collections. SynchronizedList (new ArrayList (…). ); , you can achieve synchronization

LinkedList source code analysis

concept

  • LinkedList is implemented based on a LinkedList, so let’s explain what a LinkedList is. A linked list, originally a concept of C/C++, is a linear storage structure. It means that the data to be stored is stored in a storage unit. This storage unit not only stores the data to be stored, but also stores the address of the next storage unit (the address of the next storage unit is necessary, Some storage structures also store the address of the previous storage unit). Each time the data is searched, the next storage unit is searched by the address of the next storage unit in a storage unit.
  • To understand:
    • LinkedList is a two-way LinkedList
    • That is, each element in the list stores the addresses of the elements before and after it, in addition to its own value, so it is easy to get the elements before and after it based on the current element
    • The following node of the tail element of the list is the head node of the list; The first node of the list is the last node of the list.
    • Since it is a two-way LinkedList, there must be a basic storage unit. Let’s look at the most basic storage unit for LinkedList.

For a single necklace table his hand tore a, interested can go to see

🔥 The most complete set of Java container data structures ever (hand-torn list)

Inheritance structure and hierarchy

So linkedList does not have the function of RandomAccess. It must be traversed one by one. The conclusion is: ArrayList iterates faster with for than iterator, LinkedList iterates faster with iterator than for

Another difference between LinkedList and ArrayList is that ArrayList directly inherits from AbstractList, whereas LinkedList inherits from AbstractSequentialList, and then from AbstractList. In addition, LinkedList implements the Dequeu interface, a two-ended queue.

Deque dual-ended queue

Deque double-endian queue, I haven’t talked about this before, but I’ll fill it out myself

A deque (full name double-ended queue) is a data structure that has the properties of queue and stack. A queue is an ordered list that can be implemented as an array or a linked list.

Elements in a two-ended queue can pop up from both ends, with restricted inserts and deletions occurring at both ends of the table. A two-enqueued queue can be joined and dequeued at either end of the queue.

Follow the first-in, first-out principle:

  • Data that is put into the queue first is taken out first.
  • What is put in later is taken out later

Let’s take a look at the queue method

  • Add and offer both indicate that the insertion difference is an error on a failure, and false on a failure
  • Remove and poll both indicate that the deletion is successful and returns the first element in the queue which throws an exception when the queue is empty. Poll returns null if remove fails
  • Element peek returns the first queue element but does not remove the first queue element. Element throws an exception when the queue is empty. Peek returns null

So to summarize, queues are very simple, especially simple like this. There are only three operations join delete view and all of them are for the head of the queue.

Let’s take a look at Deque

In fact, the operation is similar, the queue can only operate the head of the queue, two-way queue can operate the head and tail of the queue

Tear a simple queue by hand

We know that the bottom layer of a queue can be an array or a linked list, so today we’re going to use an array to implement a simple queue

package com.atguigu.ct.producer.controller; ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** * */ public class QueueTest1 {public static void main(String[] args){system.out.println (" queue "); Queue queue = new Queue(); Queue. In (" Six-vein Magic sword "); queue. Queue. In (" 7 sell magic sword "); queue. Queue. In (" all things to all men "); queue. System.out.println(queue.out()); System.out.println(queue.out()); Class Queue {String[] a = new String[5]; int i = 1; Public void in(String m){a[i++] = m; } public String out(){int index = 0; String temp = a[1]; for(int j=1; j<i; j++){ a[j-1] = a[j]; index++; } i = index; return temp; }}Copy the code

The results of

Process finished with exit code 0Copy the code

And it’s very simple to just move all of the indices one place forward each time you come out. The queue is deep, this side is not deep, rely on you big guy himself, I am also a yellow woman to sell melons. Next, let’s talk about LinkedList

LinkedList constants

Three constants: one for the size of the set, one for the element before the queue element, and one for the element after the queue element

Consider a Node element that stores three data, one for itself, one for its precursor, and one for its successor

A constructor

LinkedList has two constructors, the first is the default empty constructor, and the second is to add an instance of an existing Collection of elements to LinkedList using the addAll() method, which we’ll look at below.

Note that LinkedList is a constructor that does not initialize the size of a LinkedList. Unlike arrays, where a defined array must have a definite size and then allocate memory, linked lists have no definite size and move Pointers to the next memory allocation.

Add elements

  • addFirst(E e)
    • Adding an element to the head of the list simply replaces the successor pointer to the head of the list
  • AddLast (E E) and Add (E E)
    • Adds the specified element to the end of the list
  • add(int index, E element)
    • Element unpacking to the specified location, this must first find the elements before and after the element, and then modify.
  • addAll(Collection<? extends E> c)
    • Appends all elements in the specified collection to the end of this list in the order returned by the iterators for the specified collection

Remove elements

Like adding elements, deleting elements is done by changing references to the previous node and to the next node.

  • Remove () and removeFirst ()
    • Removes and returns the first element from this list
  • removeLast()
    • Removes and returns the last element from the list
  • remove(int index)
    • Deletes the element at the specified position in this list
  • remove(Object o)
    • If it exists, the first occurrence of the specified element is removed from the list. Note that this removes the first occurrence, not all of the elements

Modify the element

Replaces the element at the specified position in this list with the specified element by calling the set(int index, E Element) method.

The node(index) method is used to obtain the node with the specified index position, and then modify the element of the node position.

Look for the element

Because the screenshot is not all I did not screenshot, we can look at the source code, the specific implementation is not difficult, in front of our hand tear list most also achieved

  • getFirst()
    • Returns the last element in this list
  • getLast()
    • Returns the last element in this list
  • get(int index)
    • Returns the element at the specified index
  • indexOf(Object o)
    • Returns the index of the first occurrence of the specified element in this list, or -1 if the list contains no element.

Traverse the collection

Normal for loop

The code is simple, we use the Get (int index) method of our LinkedList to iterate through all the elements.

The get(int index) method traverses all the elements preceding the index each time. For example, in the set of LinkedList above, I put A,B,C, and D as elements.

  • A total of four traversals are required:
  • First traversal Print A: Only need to traversal once.
  • Second pass to print B: need to find A first, and then find B to print.
  • Third traverse print C: need to find A first, then find B, finally find C print.
  • Print D for the fourth time: first find A, then find B, then find C, and finally find D.
  • So if the set has a lot of elements, the more time it takes to get to the end of the set (of course, the get method is optimized so that the first half of the set is traversed from the front, and the second half of the set is traversed from the back, but it still takes a lot of time). So how to improve?

Iterators Another form of iterator that is better suited to use is the foreach loop, which is also used by the underlying implementation, but we won’t cover it here

conclusion

  • List inherits Collection. It is an ordered and repeatable List.
  • Implementation classes include ArrayList, LinkedList, Vector, Stack, and so on
    • An ArrayList is implemented based on an array, which is an array queue. Can dynamically increase capacity! The thread is not safe. Array-based searches are fast, and additions and deletions are slow, because the element after it has to be reindexed if it is deleted.
    • LinkedList is implemented based on a LinkedList and is a two-way circular list. Can be used as a stack! , its search is slow, each search has to traverse the entire collection, but it is fast to add and delete, especially the end of the add, especially fast.
    • Vector is implemented based on arrays, is a Vector queue, is thread-safe! It’s pretty much the same as ArrayList, but it’s thread-safe, which means it doesn’t perform as well.

Release notes

  • The source code here is JDK8 version, different versions may vary, but the basic principle is the same.

At the end

The three implementations of List are not too difficult. Bloggers followed and found that they used to just use it, but now they are really familiar with it. The next section starts with Map, and since the underlying Set is based on Map, it comes last

I have a goal to write two or three articles a week. I hope I can keep it up for a year. I hope you can give me more suggestions so that I can learn more and make progress together.

Daily for praise

All right, everybody, that’s all for this article. All the people here are talented.

Creation is not easy, your support and recognition, is the biggest motivation for my creation, we will see in the next article

Six pulse excalibur | article “original” if there are any errors in this blog, please give criticisms, be obliged!