[자료구조] 배열과 링크드 리스트

배열 (Array List)

장점 : 직관적이고 데이터의 접근속도가 빠르다. 비교적 다른 자료구조에 의해 저장공간의 낭비가 없다.
단점 : 삽입과 삭제에 엄청난 시간이 소모된다. 크기가 정적이기 때문에 데이터 포화시 크기를 재조정 하는 연산을 해주어야 하며, 적지않은 비용이 소모된다.

배열의 삽입

1234567   ->나름 인덱스
abcefgh  이곳에 빠진 d를 삽입해봅시다.

12345678
abcefg h
abcef gh
abce fgh
abc efgh
abcdefgh  음... 이와같이 총 5번의 작업을 하게됨. 만약 배열의 길이가 100만 넘어가도 후월털러털..

삭제는 안함

링크드리스트 (Linked List)

:여러게의 노드가 선형으로 이루어져있으며, 각 노드는 데이터와 다음 노드를 가리키는 링크로 이루어져있다.

장점 :  데이터 크기와 상관없이 삽입과 삭제에 있어서 용이하다. 2단계의 수행단계면 충분. 연속적인 기억장소의 할당이 필요하지 않다. 시작 주소만 알고있으면 연속된 데이터에 접근하기가 쉽다.
단점 : i번째 데이터를 추출할 시에 head부터 n-1번만큼 링크를 타고들어가야 하기 때문에 탐색속도에서 약점을 가지고 있다. 포인터의 사용으로 저장공간의 낭비를 초래할 수 있다.

head....a-b,,,, tail    에 노드  c를 삽입

c 링크를 b로 설정
a 링크를 c로 설정 (과 동시에 a-b링크는 삭제)

a-c-b 에서 c를 삭제 시

a링크를 b링크에 연결
c링크를 null로 설정

그런데..
배열이나 링크드 리스트에서 값이 100인 값을 찾고싶을땐 뭐 비슷한 시간이 걸리겠지..?
가 아니라 배열은 메모리에 연속적으로 적재가 된다. 반면 링크드 리스트는 노드 하나하나가 드레곤볼처럼 여기저기에 저장이 되기 떄문에 포인터로 다음 노드를 찾는데 그만큼에 탐색시간이 오버플로우 된다는 것이다.

여튼 색인탐색에서는 배열 O(1) vs 링크드 리스트 O(n) 이고
값탐색(?) 에서는 배열 O(n) vs 링크드리스트 O(n)+알파 라는 것이다.

무튼 탐색은 배열 / 삽입삭제는 링크드리스트, 따라서 경우에 따라 더좋은 자료구조를 선택하도록 하자