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: 고정점으로부터의 위치

3번에 접근하기 위해서 큐브 3개를 지나쳐와야 한다 즉, 8*3 24byte

2번 요소와 0번 요소의 오프셋은 int형 *2라 정확히 8byte더라. 즉, 메모리에 순차적으로 존재한다는 것을 알 수 있다.

 

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.

초기엔 size가 3이었다가 새로운 요소를 추가하고 size가 4로 변환된 것을 볼 수 있음.

 

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.

List Node의 구성

 

Linked List

Zero or more ListNode elements linked together form a Linked List.

head pointer = 리스트의 시작 /null pointer = 포인터가 어떠한 객체를 가리키지 않음. 즉 끝

• 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

인덱스 4번에 접근하려면 앞선 모든 노드를 거쳐야 한다. 바로 연결되는 화살표는 없다.

thru노드를 갱신해가며 원하는 인덱스의 노드에 접근하기

 

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

new를 사용해 heap에 적재되도록 하겠음. 즉, 함수 실행 주기 넘어서 살아있게끔

 

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.