1) 배열(Array)
특성
- 연속된 메모리 공간에 순차적으로 저장된 데이터 모음
- 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하여 indexing 및 slicing이 가능(자바스크립트에서는 배열 요소의 인덱스가 연속적이지 않아도 되며, 따라서 특정 배열 요소가 비어 있을 수도 있다)
- indexing : index를 사용해 특정 요소를 리스트로 부터 읽어들이는 것
- slicing : 요소에 특정 부분을 따로 분리해 조작하는 것
- 대부분에 프로그램 언어에서 동일 타입의 데이터를 저장 (자바스크립트는 다른 타입들과 함께 저장할 수 있지만, 그렇게 사용하는 경우는 거의 없다)예를 들어 배열이 int타입인 경우 정수 요소만 저장할 수 있으며 double, float, char 등과 같은 다른 타입의 요소는 저장할 수 없다
- 배열을 구성하는 각각의 값을
요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는인덱스(index)라고 한다
- 배열은 선언할 때 크기를 정하면, 그 크기로 고정된다. (이 역시 자바스크립트에서는 조금 다르다)
- 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있다
- 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다
👀 자바스크립트에서 배열은 도대체 어떤 거지?
😊장점
- 구현이 쉽다.
- 참조를 위한 추가적인 메모리가 필요하지 않다
- 연속적이므로 메모리 관리가 편하다
- 인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있다
- 기록 밀도가 1이기 때문에 공간 낭비가 적다
- 리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 안되지만, 배열은 부가정보 없이 데이터만 저장하기 때문에 기록밀도가 1
😫단점
- 배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없다
- 중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로부터 위에 있는 모든 요소들을 이동시켜주어야 한다→ 삽입 및 삭제에 비용이 많이 들어감!
- 배열의 크기가 대부분 정적으로 결정되기 때문에 삽입과 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하는 것이 어렵고, 이로 인해 오버플로나 저장공간의 낭비를 초래할 수 있다
배열을 주로 사용하는 경우
- 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
- 다차원 데이터를 다룰 때
- 어떤 특정 요소를 빠르게 읽어야 할 때
- 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때
배열의 시간복잡도
| Operation | average case | worst case |
| read | O(1) | O(1) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |
| search | O(n) | O(n) |
2) 연결 리스트(Linked List)
특성
- 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
- 연결 리스트는 데이터와 포인터로 구성된 노드 간의
연결(link)을 이용해서 리스트를 구현한 자료구조
- 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성
- 연결 리스트는 데이터와 포인터로 구성된 노드 간의
- 연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 연결이 필요
- 연결되어있는 구조이기 때문에 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여 순차 접근만 가능
연결 리스트는 아래 그림과 같이 포인터를 사용하여 각 노드를 연결
Head는 리스트의 처음을 나타냄
노드는데이터와 다음 노드를 가리키는Next 포인터로 구성
- 각 노드는 next 포인터를 사용하여 다음 노드와 연결됨
- 마지막 노드는
null을 가리켜 리스트의 끝을 나타냄
😊장점
- 크기가 가변적임
- 메모리가 허용하는 만큼 커질 수 있음
- 삽입 삭제가 쉬움
- 삽입 삭제 시에 데이터 이동이 필요 없음
😫단점
- 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 접근해야 함.
- 이진 탐색 수행 불가능
- 포인터를 위한 추가 메모리 공간이 필요함.
연결리스트 종류
연결 리스트는 연결 방향에 따라 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다
단일 연결 리스트(Singly Linked Linear List)
각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다. tail은 가장 마지막이므로 다음을 가리키는 포인터를 갖지 않는다.
이중 연결 리스트 (Doubly Linked Linear List)
구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다
원형 연결 리스트 (Circularly Linked Linear List)
일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조. 단일 연결 리스트의 tail에 포인터가 추가된 형태로 tail의 포인터는 head를 가르켜 원형이 되도록 한다.
시간 복잡도(Time complexity)
| operation | time |
| Insertion | O(1) |
| Deletion | O(1) |
| Search | O(n) |
