The difference between an array and a linked list

A thousand miles kuibu, thousands of rivers. Make a little progress every day, and one day you’ll be a big shot

Wen speaking

In Java, arrays and lists are used in many places, and there are also two combinations called array lists, commonly known as hash tables. The underlying data structure of a HashMap is a hash table. Far, far, far, we don’t talk about hashMaps, we talk about arrays and linked lists;

An array of

Array is the most commonly used data structure. It is characterized by fast data query and slow data insertion. The time complexity of query is O(1) and the time complexity of insertion is O(n).

The cow * family goes to school to study, the school has four people to sleep and five people to sleep, Daniel, two cows, three cows, four cows together live in the four people to sleep, every day five lack one; One day, they met the calf in the game, and learned that the calf was also their school, so they invited the calf to live with them, but they can only live four people, how to do this? So they applied to the school (system) for a new six-person bed (new memory space), so the school gave them a new six-person bed, so they all moved to the six-person bed, the calf also did it, and after five nights every day, happy;

Later, other students saw what the cows did and applied to the school as well. Finally, the university found a problem: students spent a lot of time on the way from the old dormitory to the new dormitory in order to live in the new dormitory.

Some people will say, that at the beginning of the arrangement Daniel, two cattle, three cattle, four cattle live 5 people to sleep is not good? So they don’t have to move (this is equivalent to specifying a size for the array when we initialize it); It’s a good idea, but if they don’t know the calf, the calf won’t move in, so the four of them will always live in a five-person bed, and it’s a waste of space;

One day, the teacher to find into the new dormitory of the calf talk, a look that the calf in no. 4 bed, once found the calf (query data fast), asked him in this dormitory living habits, small cow thought, every day five black, you say I am not used to the habit!!

The list

Linked list we usually use less, it is characterized by: insert data fast, query data slow, query time complexity is: O(n), insert time complexity is: O(1), its characteristics and array is the opposite;

After many days and nights of fighting, the cow decided it was time to go out and play. Since the calf had moved in, it had been night and day, and he hardly knew what the outside world looked like. They are going for a walk in the amusement park.

After coming to the amusement park, a group of people like just put out of the same, to everything is full of freshness, around. While walking around, the careful Daniel found a piece of paper on the ground. It read: “Young man, do you desire power? If you want power, come to me on the pirate ship!” “Daniel quickly find other partners, go together; When they got to the pirate ship, they found a message on the ship: “Power comes from the ferris wheel, please go to the ferris wheel.” So a group of people went to the ferris wheel again. There, they finally passed the mysterious power — toxic chicken soup: How strong your heart is, how strong your power is; The Mavericks are going through a lot of trouble to find that power.

You can see that each element holds the address of the next element, so if you want to look for one of these elements, you have to start from scratch to find it. This is slower. However, they add elements so quickly that they can appear at random somewhere in the amusement park by indicating the address of the new element in the preceding element;

Send us a comparison chart

Time complexity comparison table