array

define

An array is collection of items stored at contiguous memory locations. The idea is to store multiple items of same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

complexity

space

O(n)

time

write by index

write by index: O(1)

read by index

read by index: O(1)

worst case: O(n)

best case: O(1)

average: O(n/2)

sort

details in the below picture：

advantage

  1. Arrays have better cache locality that can make a pretty big difference in performance.
  2. In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.
  3. The requirement of memory is less due to actual data being stored within the index in the array. As against, there is a need for more memory in Linked Lists due to storage of additional next and previous referencing elements.
  4. Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.

disadvantage

  1. The size of the arrays is fixed.
  2. Inserting a new element in an array of elements is expensive. the same as delete a element.
  3. In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.

list

define

a Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next one .

a Linked list is a collection of some link nodes, which are not contiguous im in memory like the array. Instead, each node points to the next.

space

O(n)

time

no index

add

add: O(1)

delete by list node

O(1)

delete by value：

worst case: O(n)

best case: O(1)

average: O(n/2)

search

worst case: O(n)

best case: O(1)

average: O(n/2)

advantage

  1. Dynamic size.
  2. Ease of insertion/deletion.

disadvantage

  1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
  2. Extra memory space for a pointer is required with each element of the list.
  3. Arrays have better cache locality that can make a pretty big difference in performance.

refence

  1. Introduction to Arrays
  2. Array data structure
  3. Linked List vs Array
  4. Binary Tree Data Structure

欢迎关注

欢迎关注微信公众帐号：沉风网事(savewind)

沉风网事