Machineboy空
Ordered Data Structures # WEEK1 : Arrays VS Linked Memory 개념 본문
1.1 Arrays
An array stores data in blocks of sequential memory.
so that as soon as one element ends, the next element begins.
Array Limitation #1 : 모든 요소가 같은 데이터 타입
- Elements are all the same type:
- ex) An integer array must only contain integers.
- The size(number of bytes) of the type of data is known.
We can calculate the offset to any given index from the start of the array:
*offset: 고정점으로부터의 위치
Array Limitation #2 : 고정된 크기
- Arrays have a fixed capacity
- Arrays must store their data sequentially in memory
- The capacity of an array is the maximum number of elements that can be stored.
- The size of an array is the current number of elements stored in the array.
An array is full when the size of the array is equal to the capacity.
The only way to add another element is to allocate a new, larger array and copy over all of the data:
std::vector
vector과 array의 작동하는 방식이 같다. 요청된 공간만큼을 재설정하여 만든 후 , 기존의 것을 복사.
The std::vector implements an array that dynamically grows in size automatically. However, all properties remain true:
- Array elements are a fixed data type
- At any given points, the array has a fixed capacity
- The array must be expanded when the capacity is reached.
vector와 array가 다른 자료구조의 개념이 아닌건가?
vector는 array의 원리를 사용한 것?
array[i]로 한번에 접근하는 것 처럼 보이지만 시작점으로부터의 offset을 구해 접근하는 거구나.
시간 복잡도 o(1)
1.2 Linked Memory
Linked memory stores data together with a "link" to the location (in memory) of the next list node:
instead of searching all of the data sequentially in memory
several advantages over array.
List Nodes
A list node refers to pair of both the data and the link.
Linked List
Zero or more ListNode elements linked together form a Linked List.
- A pointer called the "head pointer" stores the link to the beginning of the list.
- A pointer to nullptr marks the end of the list
List Runtime
In a list, the time it takes to access a given index grows based on the size of the list.
In contrast, an array can access any element in a constant, fixed amount of time, There for accessing a given index, an array is faster than a list.
List::insert
Objective: Add an element to the list
List Capacity : 삽입 용량이 자유롭다
In a list, the capacity is bounded only by the memory available on the system.
In contrast, an array has a fixed capacity. A list is a more flexible data structure than an array.
Data Type
In both arrays and lists, all data within an instance of a container must be the same type.
Linked Memory
- Linked memory stores data in "nodes" linked together by "links"(pointer).
- A basic linked memory structure is a Linked List, which consistes of zero or more ListNodes lined together and a head pointer.
- A linked list provides a flexible alternative to an array.