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)
을 이용해서 리스트를 구현한 자료구조
- 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성
- 연결 리스트는 데이터와 포인터로 구성된 노드 간의
- 연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 연결이 필요
- 연결되어있는 구조이기 때문에 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여 순차 접근만 가능
연결 리스트는 아래 그림과 같이 포인터를 사용하여 각 노드를 연결
![](https://blog.kakaocdn.net/dn/bsuFa6/btqSDuBL2eI/96valZHnFIVmkafB0Jt4xk/img.png)
Head
는 리스트의 처음을 나타냄
노드
는데이터
와 다음 노드를 가리키는Next 포인터
로 구성
- 각 노드는 next 포인터를 사용하여 다음 노드와 연결됨
- 마지막 노드는
null
을 가리켜 리스트의 끝을 나타냄
😊장점
- 크기가 가변적임
- 메모리가 허용하는 만큼 커질 수 있음
- 삽입 삭제가 쉬움
- 삽입 삭제 시에 데이터 이동이 필요 없음
😫단점
- 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 접근해야 함.
- 이진 탐색 수행 불가능
- 포인터를 위한 추가 메모리 공간이 필요함.
연결리스트 종류
연결 리스트는 연결 방향에 따라 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다
단일 연결 리스트(Singly Linked Linear List)
각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다. tail은 가장 마지막이므로 다음을 가리키는 포인터를 갖지 않는다.
![](https://blog.kakaocdn.net/dn/x8iTE/btrRAEFj7K6/DKKIOgRnzSWjOKIWK75tNK/img.png)
이중 연결 리스트 (Doubly Linked Linear List)
구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다
![](https://blog.kakaocdn.net/dn/dFETca/btrRBfSQnxv/FdimTuOp6lLQKxn1Q1P6m1/img.png)
원형 연결 리스트 (Circularly Linked Linear List)
일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조. 단일 연결 리스트의 tail에 포인터가 추가된 형태로 tail의 포인터는 head를 가르켜 원형이 되도록 한다.
![](https://blog.kakaocdn.net/dn/cuRV4Z/btrRFfxvwAZ/EY8q7npIr12DRGHWFce44k/img.png)
시간 복잡도(Time complexity)
operation | time |
Insertion | O(1) |
Deletion | O(1) |
Search | O(n) |