배열
: 정적 자료구조라고 불립니다. 배열을 만들기 위해서는 미리 크기를 정해놓게 되고, 그렇게 되면 해당 크기 만큼의 연속된 메모리 주소를 할당받게 됩니다.
-> 연속된 메모리를 할당? = 인덱스(index)를 갖게 됨 !
index를 갖게 된다는 것은 즉 임의 접근이 가능하다는 장점이 있어서 접근과 탐색에 용이합니다.
하지만 "크기를 미리 정해놓았기 때문에" 수정은 불가능하며 해당 배열 크기 이상의 데이터를 저장할 수 없다는 단점
이 있습니다.
index 기반의 자료구조
연속적으로 할당된 기억 공간
배열의 크기가 n이라면 n개의 자료를 하나의 주소( 0번째 index 주소)로 접근할 수 있음
링크드리스트
: 동적 자료구조라고 불립니다. 그러므로 크기를 정할 필요가 없고, 배열처럼 연속된 메모리 주소를 할당 받지 않습니다.
대신 각 원소를 노드(Node)라고 부르며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있는, 연결되어 이어진 형태 이다.
링크드리스트는 크기를 정해 놓지 않았기 때문에 크기의 제한이 없어서, 데이터 추가, 삭제가 자유롭다는 장점
이 있다.
반면에 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능합니다. 즉, 데이터를 탐색할 때 순차적으로 접근해야 한다는 단점
포인터 기반의 자료구조
메모리 공간에 임의의 위치에 이산되어 저장되어 있음
한 원소는 다음 원소를 가리키는 link를 가지고 있음
배열은 index를 가지고 있기 때문에 탐색은 O(1)의 시간복잡도를 가집니다.
삽입의 경우는 맨 뒤라고 한다면 O(1) 의 시간복잡도를 가지지만 맨 뒤가 아닌 나머지는 O(n) 입니다.
링크드리스트는 추가, 삭제가 용이하기 때문에 삽입은 맨앞일 경우 O(1), 맨 앞이 아닌 나머지는 O(n) 입니다.
배열과 반대로 탐색은 O(n)의 시간복잡도를 갑니다.
==> 배열의 탐색은 O(1)
링크드 리스트의 탐색은 O(n)
배열
은 정보를 저장할 때 많이 쓰인다. 물건(정보)가 일렬로 줄이 세워져있는 바구니 역할.
불규칙적인 정보를 저장하거나, 이후에 다시 사용할 정보를 저장하거나 할 때 배열을 활용합니다.
const foodList = ['짜장면', '돈까스', '초밥', '김치볶음밥', '햄버거'];
const randomIndex = Math.floor(Math.random() * foodList.length);
const todayFood = foodList[randomIndex];
console.log(todayFood); // foodList 중 랜덤으로 하나의 음식 이름이 나온다.
링크드리스트
의 경우는 음악 플레이어 앱에 이전곡과 다음곡이 연결되어 있는 것, 포토샵의 history 기능에 링크드 리스트를 활용했다고 함 !
포토샵의 history 기능은 내가 작업한 어느 시점으로 다시 되돌아가거나 다시 최근으로 돌아올 수 있음.
💟참고자료
배열/링크드리스트
배열/링크드리스트의_특징