목차

배열
연결 리스트

엄청나게 밀려버린 TIL... 눈물을 흘리며 작성합니다.😂

대표적인 선형 자료구조 두 가지를 정리해 보았다.

배열

• 연관된 데이터를 연속적인 형태로 가진다.
• 저장된 데이터는 인덱스를 통해 꺼내쓰거나 새로운 데이터를 넣을 수 있다.
• 자바스크립트에서 배열을 사용하다보면 헷갈릴 수 있는데, 배열은 고정된 크기를 가진다.
• 장점
  • 인덱스를 통해 상수 시간(O(1))만에 원소를 찾을 수 있다.
• 단점
  • 배열은 중간에서 요소를 삭제하거나 추가할 경우, 선형 시간(O(n))이 걸린다. (생기는 빈 공간만큼 당기거나, 추가하는 위치의 뒤로 모든 요소를 밀어야 하기 때문이다.)

추가와 삭제가 반복된다면 권장하지 않고, 탐색이 많은 경우에 더욱 유리한 자료구조라고 할 수 있다.

자바스크립트의 Array는 배열이 아니다!
실제로는 해시 테이블로 구현되어 있다고 한다.
우리가 배열에 숫자 값이 아닌 문자열 등의 값을 키로 사용할 수 있는 것도 실제로는 배열이 해시 테이블로 구현 되어있기 때문이다.(근본적으로는 객체와 같기 때문이다.)
출처 : https://poiemaweb.com/js-array-is-not-arrray

자바스크립트의 Array는 JS 엔진의 힙 영역에 주소를 밸류로 저장하고, 콜 스택에 해당 주소를 쌓아놓는다. 이 경우에 스택의 밸류가 변경되면 힙 영역의 주소 밸류가 변형되는지 궁금했다. 이 부분은 이번 주 스터디에서 해결할 수 있었는데, 힙에 밸류로 설정된 주소는 변하지 않고, 스택에서 값만 바뀐다고 한다. 길이가 동적으로 관리되기 때문이다.

연결 리스트

• 각 요소를 포인터로 연결하여 관리하는 선형 구조이다.

• 각 요소는 노드라고 부르며 데이터 영역 포인터 영역으로 구성된다.
  포인터 영역 : 다음 노드를 가리키는 역할

• 연결 리스트는 배열과 상반된 특징을 갖는다.

  	배열	연결리스트
  메모리 영역	순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용한다.	순차적이지 않아 퍼져있다. 퍼져있는 메모리 영역을 알기 위해 포인터를 사용하여 각 영역을 참조하게 된다.
  요소 추가	O(n)	O(1)
  요소 삭제	O(n)	O(1)

• 연결 리스트에는 세 가지 종류가 있다.

1. 단일 연결 리스트(Singly Linked List)
   • head에서 tail까지 단방향으로 이어지는 연결리스트
   • 노드는 value, next(다음 노드를 가리키는 포인터 영역)로 이루어짐
2. 양방향 연결 리스트(Doubly Linked List)
   • 노드가 value, next, prev 로 구성되어서 이전 노드와 다음 노드를 참조하여 연결되어 있음
   • 단일 연결 리스트보다 자료구조의 크기가 좀 더 큰 단점이 있지만, 큰 단점은 아님
3. 환형 연결 리스트(Circular Linked List)
   • tail이 head로 연결되도록 고리를 만드는 연결리스트
   • 중간에서 탐색하더라도 한 바퀴를 전부 탐색 할 수 있음
   • cycle이 생기므로 탐색 종료 조건이 있어야 함

동작 이해를 통해서, Garbage Collection의 기준에 대해서 명확히 이해할 수 있었다.
현재 노드가 다음을 참조하고 있고, next 와의 참조가 끊어진 경우에 해당 노드가 참조를 하고 있다 하더라도 Garbase Collection의 대상이 된다. Garbage Collection은 무엇을 참조하는 가가 아니라 누가 참조하고 있는가가 기준이라는 것을 좀 더 명확히 할 수 있었다.

참고 자료 및 강의

프로그래머스 프론트엔드 데브코스 Day3 [강의] 배열, 연결리스트