10/11 - 배열과 리스트, 연결리스트 + 관련된 데이터자료

배열과 리스트, 데이터


1.데이터

int x = 10 // ==>stack 영역에 저장

int의 사이즈는 4byte다. 이는 무엇이냐? 메모리 영역에 4칸이 할당된다는 것
해당 공간은 40억개의 공간을 가지므로, 수의 크기에는 크게 관계없다.

즉, 변수의 int의 사이즈는 4byte로 고정되므로, 변수가 변해도 상관없이
할당 공간이 변화하지 않는다.

+만약 이보다 큰 경우 long을 사용해야 함.



string의 사이즈는 '한 글자' 당 2byte다. (char당 2byte)

만약 string name = "Woo" 에서
name = "WooMin"으로 변경된다면

6byte에서 12byte의 공간을 재할당 받는다.(기존 공간에 붙이는게 아닌 완전히 새로운 저장공간을 사용한다.)


그럼 기존에 할당된 사용하지 않는 공간들은 어떻게 되는가?
GC(가비지 콜렉터)가 일정 시간 이후 한번에 제거한다.
==>가비지가 많이 쌓이게 되며, 성능에 영향을 준다.


+그럼 같은 글자수는 같은 공간에 받나? ==> 아니다.
같은 글자수를 가진 stirng이더라도 새로운 공간을 할당받고, 기존 공간은 버려진다.

그럼 stirng의 사용은 성능 저하를 불러오는데 어떻게 해결하여야 하나?

★string Builder를 사용한다.

ㅡㅡㅡㅡㅡㅡ


2.배열 / 리스트 / 연결 리스트 (이들 모두는 heap 영역이다.)


배열과 리스트 연결 리스트의 차이는 무엇인가??

배열 : 사이즈가 정해져있다.

리스트 : 사이즈가 정해져있지 않고 추가,제거가 가능하다.

위 두가지는 서로 비슷하다.
ㅡ

★연결리스트 : 



ㅡㅡ

Array : 배열(크기 고정)

1)중간 데이터가 제거(변형)된다고 하더라도, 해당 공간이 그대로 남아있다.

int[5] nums 라는 변수가 있다면
4byte 크기의 공간 0~4까지가 메모리에 생성되는 것이다.

만약 배열의 중간에 값을 넣고싶다면,
원하는 부분의 값을 변경하고, 뒤의 속성들을 한칸씩 뒤로 밀어 새로 작성해야한다.


2)배열의 장점?
여러 자료형을 사용할 수 있고
원하는 속성을 찾을 때 index에서 무조건 한번에 찾는다.


List : 리스트(크기 가변)
1)중간 데이터가 제거되면, 해당 공간이 사라지고, 뒤의 속성이 앞으로 당겨와지게 된다.

리스트를 생성할 때

new List<int> 를 생성한다 했을 때,
내부적으로는 배열로 되어있다. [기본적으로 int[4] 늘어난다면 기존에서 제곱한다. ]

List<int>예시

names.Add(10),,,names.Add(12)...names.Add(22)...names.Add(33)
의 기본생성 4칸을 전부 사용하고, 추가적으로 Add 하게 된다면?

string의 경우와 똑같이 완전히 새로운 공간을 할당받는다.
그러니 가능한 예상 가능한 공간의 크기를 미리 지정한 List를 생성하는것이 좋다.

위에서 설명했듯, 만약 중간의 데이터를 제거한다면,
뒤의 속성을 당겨오고

1, 2, RemvoeAt, 4, 5 

1, 2, 4, 5

중간에 데이터를 추가한다면,
뒤의 속성을 한칸씩 민다.

1, 2, Add, 4, 5

1, 2, 3, 4, 5



만약,
1~100까지의 수를 가진 List가 있다고 가정하자
중간에 데이터를 추가 삭제한다면(Worst case 2번째 수를 추가하거나 제거)
상당한 수의 순서 이동이 발생하므로, 
비효율적이 된다.


ㅡㅡㅡㅡㅡ


3. 연결 리스트

int nums<int>라는 리스트가 있다면,

head와 tale이라는 노드(1칸)가 있다.


앞의 인트와 리스트와는 다르게,
한줄로 쭉 연결된것이 아닌,

여기저기 흩어진 노드들을 주소 연결(next)만 해준것


즉, 추가 삭제 시 주소만 변경하여 주면 끝이다.
==> 삽입 삭제가 자유롭다.(List의 경우와 큰 차이가 있음)
추가 삭제 시 O(1)을 가진다.



데이터를 찾아올 땐? 어떻게 해야할까
접근하는 경우엔 int와 List에 비해 조금 불리하다.
왜? 호출 시 무조건 head부터 꼬리에 꼬리를 물며 
tale까지 호출된 주소를 찾아 올라가므로