배열(Array)
배열 : 정적 자료구조라고 불립니다. 배열을 만들기 위해서는 미리 크기를 정해놓게 되고, 그렇게 되면 해당 크기 만큼의 연속된 메모리 주소를 할당받게 됩니다.
-> 연속된 메모리를 할당? = 인덱스(index)를 갖게 됨 !
index를 갖게 된다는 것은 즉 임의 접근이 가능하다는 장점이 있어서 접근과 탐색에 용이합니다.
하지만 "크기를 미리 정해놓았기 때문에" 수정은 불가능하며 해당 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있습니다.
[ 배열의 특징 ]
-
index 기반의 자료구조
-
연속적으로 할당된 기억 공간
-
배열의 크기가 n이라면 n개의 자료를 하나의 주소( 0번째 index 주소)로 접근할 수 있음
연결리스트(Linked List, 링크드리스트)
링크드리스트: 동적 자료구조라고 불립니다. 그러므로 크기를 정할 필요가 없고, 배열처럼 연속된 메모리 주소를 할당 받지 않습니다.
대신 각 원소를 노드(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 기능은 내가 작업한 어느 시점으로 다시 되돌아가거나 다시 최근으로 돌아올 수 있음.
💟참고자료
배열/링크드리스트
배열/링크드리스트의_특징
