What are the differences between linked lists and arrays?

The array is a linear structure and can be indexed directly, that is, to get the i-th element, just a[i]. A linked list is also a linear structure. To get the i-th element, you only need to use a pointer to traverse it backwards i times. It seems that linked lists are more troublesome and less efficient than arrays.

Thinking of some of the subtle differences among these similarities, their real differences gradually emerged: Why is the efficiency of linked lists lower than arrays? Let’s start with the initialization of both. The array does not need to be initialized because the elements of the array are in the stack area of ​​the memory and the system automatically applies for space. The node elements of the linked list are in the heap area of ​​the memory, and each element must manually apply for space, such as malloc. In other words, arrays allocate memory statically, while linked lists allocate memory dynamically. Why use linked lists when they are so troublesome? Can't arrays completely replace linked lists? To return to this question, just think about how we completed the student information management system. Why use linked lists at that time? Because operations such as insertion and deletion in the student management system are very flexible, while arrays have a fixed size and cannot be inserted or deleted flexibly and efficiently. Because heap operations are more flexible. Every time you insert an element into the array, you need to move the existing elements, but the linked list elements are on the heap, so there is no need for such trouble.

Having said so much, the differences between arrays and linked lists are summarized as follows:

• Arrays allocate memory statically, and linked lists allocate memory dynamically;

• Arrays are continuous in memory, linked lists are not continuous;

• Array elements are in the stack area, and linked list elements are in the heap area;

• Array Using subscript positioning, the time complexity is O(1), and the time complexity of locating elements in a linked list is O(n);

• The time complexity of inserting or deleting elements in an array is O(n) , the time complexity of the linked list is O(1).

The above is the detailed content of What are the differences between linked lists and arrays?. For more information, please follow other related articles on the PHP Chinese website!