[자료구조] Array와 Linked List

Array

• index로 element에 접근이 가능한 자료구조
• 일반적으로 논리적 저장 장소와 물리적 저장 장소가 같다.
• 찾고자하는 원소의 index를 알고 있으면 O(1)을 갖는다.
• 배열의 삭제 작업이 발생하면, 원소 접근 O(1)을 수행하고 빈 공간을 만든 다음 삭제한 원소보다 인덱스가 큰 원소들이 이동하는 비용이 발생하게 되어 O(n)을 수행하게 된다. ( worst case도 O(n) 수행 )
• 배열의 추가 작업도 모든 원소들의 인덱스를 이동하는 비용이 발생하여 O(n)을 수행한다.

• 일반적인 의미의 배열은 메모리 영역을 연속적으로 사용한다.
• 이러한 배열은 밀집 배열(dense array)이라고 한다.
• 하지만, 자바스크립트의 배열은 배열 요소를 위한 각각의 메모리 공간이 동일한 크기를 갖지 않아도 되며, 연속적으로 이어져 있지 않아도 된다.
  • 이렇게 배열의 요소가 연속적으로 이어져 있지 않은 배열을 희소 배열(sparse array)이라고 한다.
  • 이런 이유로 갖는 장단점은 다음과 같다.
    • 인덱스로 배열 요소에 접근하는 경우, 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖는다.
    • 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다.

Javascript Array

• 자바스크립트에서 배열은 *참조 자료형 타입이다.
  • 자바스크립트는 원시 자료형과 참조 자료형 타입으로 구분된다.
  • 원시 자료형(Primitive data type)은 string, number, boolean, undefined, null, symbol 이 있다.
  • 참조 자료형(Reference data type)은 Array, Object, function(){} 이 이있다.
• 자바스크립트의 배열은 일반적인 배열의 동작을 흉내낸 해시 테이블로 구현된 객체이다.
• 배열 기초 메소드
  • isArray() : 인자 속 변수, 데이터, 값이 배열이면 true/false
  • indexOf(el) : el의 인덱스 번호를 찾아 반환, 못 찾으면 -1 반환
  • includes(el) : el 데이터가 들어있으면 true/false (대소문자 구분)
  • length() : 배열 길이를 반환
  • slice(begin, end) : 인자만큼 잘라서 반환
  • unshift() : 배열의 맨 앞에 element 추가
  • shift() : 배열의 맨 앞에 index 삭제
  • push() : 배열의 맨 뒤에 element 추가
  • pop() : 배열의 맨 뒤에 index 삭제
  • split() : 문자열을 해당 인자를 기준으로 구분하여 반환
  • join() : 문자열을 해당 인자를 기준으로 합쳐서 반환
  • 삽입과 삭제 예시
• slice 같은 경우는 메소드를 사용한 상태와 사용하고 난 상태가 다르지 않아 immutable하다.
• push, pop, shift, unshift는 상태가 서로 다르기 때문에 mutable하다.
• 그 외 내장 메소드 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array

Element Search

• 배열 원소 검색에는 선형 검색과 이진 검색으로 나뉜다.
• 선형 검색 (Linear Search)
  • 첫 번째 요소부터 차례대로 찾으려는 원소가 있는지 검색한다.
  • 모든 요소를 확인하므로 정렬되지 않은 배열에서도 사용가능하다.
  • O(n)의 시간복잡도를 가진다.
• 이진 검색 (Binary Search)
  • 분할 정복 알고리즘에 따라 중간에 있는 요소부터 비교한다.
  • 배열을 분할하면서 찾으려는 원소가 있는지 검색한다.
  • 반드시 정렬된 배열이어야 한다.
  • O(logn)의 시간복잡도를 가진다.

Linked List

Linked List 개념

• 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다.
• 각 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다.
• 이 부분만 다른 값으로 교체하면 삭제와 삽입을 O(1)로 수행할 수 있다.
• 하지만, 원하는 위치에 원소를 삽입하고자 하면 Search 과정에서부터 첫 번째 원소부터 모두 확인해야한다는 단점이 존재한다.
• 배열과 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다.
• 이러한 과정 때문에 어떠한 원소의 삽입과 삭제를 위한 검색에 O(n)을 수행하게 된다.
• Linked List는 Tree의 근간이 되는 자료구조가 된다.
• 각 요소를 포인터로 연결하여 관리하는 선형구조로, 각 요소는 노드로 불리우고 [ 데이터 | 포인터 ] 영역으로 구성된다.
• 한 쪽 방향으로 포인터가 존재하면 단일 연결 리스트, 양쪽 방향은 이중 연결 리스트라고 한다.
• 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.

 

노션에 정리한 내용을 공유합니다 : )