연결 리스트

출처 : https://www.youtube.com/watch?v=K1PlysPgNZY&t=20s

사진 출처 : Đen @Quyetnguyen0330

1. 선형 구조란?

---

1. 자료 구조의 분류

구조	설명	종류
선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스택, 큐, 데크
비선형 구조	데이터를 비연속적으로 연결한 자료 구조	트리, 그래프

2. 리스트

종류	설명
선형 리스트
(Linear List)	- 배열과 같이 연속되는 기억 장소에 저장되는 리스트
대표적인 구조 : 배열(Array) 등
가장 간편한 자료 구조이며, 접근 구조가 빠름
순차적
자료 삽입, 삭제 시 기존 자료의 이동이 필요
연결 리스트
(Linked List)	노드(데이터의 저장 부분과 포인터 부분으로 구성된 저장공간)의 포인터(=링크) 부분으로 서로 연결시킨 리스트데이터(Data)포인터(Pointer)
연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분
순차적이지 않음
cf. 연속 리스트(순차적)
노드의 삽입, 삭제가 선형 리스트와 달리 편리
연결을 위한 포인터가 추가되어 저장공간이 추가로 필요
포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림

2. 연결리스트란?

1) 개념

• 연속된 노드(Node)의 연결체

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

2) 노드(Node)

• 연결리스트에서 사용되는 하나의 데이터 덩어리이며, 데이터 & 링크이 2가지의 필드를 담고 있는 구조

• data : 노드가 담고 있는 데이터/값, 문자열, 숫자 등등 원하는 값을 넣고 저장

• next : 링크/ 포인터 역할, 다음 노드의 주소를 저장

• 양방향 연결 리스트의 경우 prev 포인터(이전 노드의 주소)추가

3) 연결 리스트의 구조

1. 마지막 연결할 것은 없기에 null과 연결

2. 연결리스트의 첫 번째 즉, 시작 지점에 있는 것을 head라고 함

3. 연결리스트의 마지막은 tail라고 부름

4) 배열 vs 연결리스트

배열

1. 배열은 메모리 공간 안에 모든 원소들이 이어진 공간에 자리 잡음

2. 인덱스를 통해 원소 탐색을 효율적으로 빠르게 실행 가능

3. random access 가능 : 배열의 n번째 원소 방문 시 O(1) 시간으로 가능 EX. arr[3]

4. 원소 삽입 & 삭제 일반적으로 O(N) 시간 소요 ⇒ 원소 개수 대로 늘어남

5) 연결리스트

1. 이어진 메모리 공간이 아닌 불특정한 공간에 존재

2. 그렇기 때문에 포인터, 주소를 참조하는 것을 통해 연결

3. 노드의 탐색은 선형시간이 걸림

4. c를 가려면 a, b를 거쳐 감

5. random access 불가능 : 리스트의 n번째 노드 방문 시 O(N)시간 소요 ⇒ head 노드부터 n번째 노드까지 순회

6. 상황에 따라 배열보다 빨라질 수 있는 노드 삽입 & 삭제

7. 연결리스트의 노드를 맨 앞에 삽입 시켜줄 때는 head 노드의 참조위치만 달라지기 때문 O(1) 처리 가능

6) 연결리스트의 종류

Singly Linked List(단일 연결 리스트)

1. 대부분의 연결리스트의 문제의 주력

2. 다음 노드에 대한 포인터만 가지고 있다

3. 일방향이다.

Doubly Linked List(이중 연결 리스트)

1. 다음 노드에 대한 포인터와 이전 노드를 가르치는 포인터를 가지고 있다.

2. 앞 뒤로 탐색하는 게 빠르다는 장점이 있지만, 노드마다 2개의 포인터를 가져야 해서 데이터의 구조와 흐름이 복잡해질 수 있음

Circular Linked List(원형 연결 리스트)

• 이중연결리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가르친다.

6) 연결리스트 구현 방법

노드의 구현 방법

class Node{
	constructor(data){
	this.data = data;
	this.next = null;
	}
}

연결리스트

let head = new Node("a");
head.next = new Node("b");
head.next.next = new Node("c");
head.next.next.next = new Node("d");

1. 시작점 : head 변수에 새로운 노드를 a라는 변수와 함께 생성

2. head라는 노드에 next라는 참조 포인터를 새로 생성할 노드 b로 지정

3. 노드 b를 새로 생성한 노드 c로 지정

4. 마지막 노드 지정