[5.2.1] 연결리스트 - [5.2.2] 배열

선형 자료 구조 : 요소가 일렬로 나열되어있는 자료구조

- 연결리스트, 배열, 벡터, 스택, 큐

배열 vs. 연결 리스트

배열은 상자를 순서대로 나열한 데이터 구조

몇번째 상자인지만 알면 해당 상자의요소를 끄집어낼수있다 = 랜덤 접근이 가능하다.  O(1)

데이터 추가 / 삭제 하기위해서 모든 상자를 옮겨야하므로 느리다. 

 

연결리스트는 상자를 선으로 연결한 형태의 데이터 구조

상자안의 요소를 알기위해서는 하나씩 상자를 열어 순차적으로 각 요소를 확인해야 한다. = 랜덤 접근이 불가능 하다. O(n)

데이터 추가 / 삭제하기 위해 선을 바꿔서 연결해주기만 하면되므로 더 빠르다. 

랜덤 접근 = 직접 접근

: 배열과 같은 순차적인 데이터가 있을때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능

 

순차적 접근 

: 데이터를 저장된 순서대로 검색해야 한다.

데이터 추가와 삭제를 많이한다 → 연결리스트

접근(참조)를 많이 한다 → 배열 

---

(1)배열 Array

인접한 메모리 위치에 있는 데이터를 모아놓은 집합

 

<특징>

같은 타입의 변수로 이루어져있다

크기가 정해져있다

중복을 허용, 순서가 있다 

 

정적 자료 구조

배열을 만들기 위해 미리 크기를 정해놓는다. = 해당 크기 만큼의 연속된 메모리 주소를 할당받는다.

= 데이터가 index 값을 갖게된다. = 임의 접근이 가능하다 = 접근과 탐색에 용이하다.

 

미리 크기를 정해놓았으므로 수정하는 것이 불가능하다. & 해당 배열 크기 이상의 데이터를 저장할 수 없다. 

 

<시간 복잡도>

index를 가지고 있기 때문에 탐색은 O(1)

삽입의 경우 맨 뒤 O(1), 맨 뒤가 아닌 나머지는 O(n)

 

<활용>

정보를 저장할때 사용.

불규칙 정보 혹은 이후에 다시 사용할 정보를 저장

---

(2)연결 리스트 Linked List

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조 

 

동적 자료 구조

크기를 정할 필요가 없다. 배열처럼 연속된 메모리 주소를 할당받지 않는다.

대신 노드Node라는게 존재하고, 그 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 갖는 식으로 연결되어있다.

 

크기를 정할 필요가 없으므로 크기의 제한이 없다 & 데이터 추가, 삭제가 자유롭다

배열처럼 연속적인 메모리 주소를 할당받지 않았기 때문에 임의로 접근하는 것이 불가능하다.

= 데이터를 탐색할때 순차적으로 접근해야한다. 

 

<시간 복잡도>

 

탐색은 O(n)

연결리스트는 삽입 삭제만 수행시간을 보면 O(1)이 됩니다.
하지만 삽입 삭제하고자 하는 값을 탐색하는 수행시간도 생각해야 합니다.

따라서 삽입의 경우 맨 앞 O(1), 맨 앞이 아닌 나머지는 O(n)

 

 

<활용> 

음악 플레이어 앱 (이전곡과 다음곡이 연결되어있음), 포토샵 히스토리 (이전 작업으로 되돌아가기 등 ) 

 

<구성>

head (헤드)

prev 포인터 

next 포인터

 

<종류>

 

싱글(단일) 연결 리스트 Single linked list

 

이중(양방향) 연결 리스트 Doubly linked list

이중 연결리스트는 각 노드가 두 개의 참조를 가지며, 하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킨다.

포인터 변수가 추가되어 단일 연결리스트보다는 자료 구조의 크기가 더 크다.

단일 연결리스트는 단방향 탐색만 가능한 반면 이중 연결리스트는 지나간 노드를 다시 탐색할 수 있다는 장점이 있다.

 

O(1)

 

원형 연결 리스트 Circular linked list

마지막 노드가 첫번째 노드를 가리키는 단일 연결 리스트 

단방향 연결리스트는 삭제와 삽입 연산이 빠르지만 탐색 연산이 느리다는 단점이 있다.

특히 헤드와 제일 멀리 떨어져있는 꼬리(tail) 노드의 삭제 연산이 최악의 연산이다.

 

하지만 원형 연결리스트는 (일반적으로) 꼬리 노드가 헤드의 노드를 가리킨다. 

 

단방향 연결리스트의 tail 삽입 삭제는 O(n)
원형 연결리스트의 tail 삽입 삭제는 O(1)

 

 

 

원형 이중 연결리스트 Doubly Circular linked list

첫 번째 노드는 마지막 노드를 가리키고, 마지막 노드는 첫 번째 노드를 가리킨다.

-> 리스트를 양방향으로 순환하게 해준다

 

 

 

<함수형>

연결리스트 자바스크립으로 구현하기

[Javascript] 연결 리스트 구현하기

<클래스형>

https://www.digitalocean.com/community/tutorials/js-linked-lists-implementation

Intro to Linked Lists via JavaScript - Part 2: Implementation | DigitalOcean

 

https://velog.io/@halley_123/%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EC%A2%85%EB%A5%98

연결 리스트의 종류