일단, JS에는 엄밀히 말해 배열이 없음
걍 리스트임
배열이 '그' 배열(Array)이 아님
Array (배열)
동일한 자료형을 가진 데이터들이 연속된 메모리 공간으로 이루어져 있는 자료구조
📍 특징
(1) 크기 | 고정 ...선언할 때 배열의 크기 결정, 변경 불가
(2) 주소 | 연속
(3) 데이터 참조 | O(1) ...index를 이용한 접근
(4) 삽입과 삭제 | O(n)
📍 장점 :
(1) 인덱스를 이용해 모든 요소에 빠르게 접근 => 조회와 같은 참조 O(1)
📍 단점
(1) 데이터 삽입/삭제가 비효율적
❓WHY❓
중간에 값을 추가하게 되면 추가할 자리를 비우고, 기존 데이터는 `복사`되어 한 칸씩 미뤄짐😨📍 배열이 사용되는 경우
데이터가 자주 바뀌지 않고, 참조가 자주 일어나는 경우
(1) 순차적인 데이터를 저장하며 중요도가 값 > 순서일 때
(2) 어떠한 특정 elm를 빠르게 읽어야 할 때
LinkedList (연결리스트)
노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식들로 데이터를 저장하는 자료구조
= 저장하려는 데이터들을 노드를 통해 메모리 공간에 분산해 할당하고 이 노드들을 서로 연결해주는 방식
노드 = 데이터와 다른 노드를 참조할 공간
포인터 = 메모리의 주소값을 저장하는 변수
📍 특징
(1) 크기 | 동적 ...리스트의 크기를 정해줄 필요가 없음
(2) 주소 | 불연속
(3) 데이터 참조 | O(n)
(4) 조회(search) | O(n)
(5) 삭제(remove) | 최대 O(n) ...이전값 알 수 없어서 O(1)
(6) 삽입(add) | O(n) -> 0(1)
❓ WHY ❓
🌸 Head 와 Tail 알고 있으므로 맨앞 or 맨뒤 삽입 => O(1)
❓ WHY ❓
🌸 데이터 추가할 때는 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결해줄 수 있기 때문
📍 장점
(1) 데이터의 삽입/삭제가 배열에 비해 효율적
❓❓ WHY ❓❓
🌸 삽입/삭제할 노드의 주변 노드들의 Link만 수정하면 된다!
=> 삽입/삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정
((다음 노드의 주소에 링크를 걸어줄 뿐, 다음 주소는 이거구나 확인만 하는 게 리스트))
📍 단점
(1) 데이터 참조에 대해서는 배열에 비해 비효율적 O(n) vs O(1)
📍 LL 이 사용되는 경우
데이터의 삽입과 삭제가 자주 일어나는 경우
