[자료구조] 연결리스트란?

유진·2023년 8월 22일

자료구조

알고리즘-자료구조

목록 보기

3/15

📝 연결리스트의 정의

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

🎯 연결리스트의 특징

<출처> programiz

각 노드는 데이터와 포인터를 가지며 포인터 변수는 다음 노드의 데이터 주소 값과 자신의 주소 값을 가진다.
연속된 노드의 연결체이다.

노드란 연결리스트에서 사용되는 하나의 데이터 덩어리이며, 데이터와 링크 두가지의 필드를 담고있는 구조이다.

🔎 연결리스트의 장단점

장점
노드의 중간 지점에서도 자료 추가와 삭제가 시간 복잡도 O(1)의 시간에 가능하다.
단점
특정 위치의 데이터를 검색하는 것에 O(n)의 시간이 걸린다.

🔗 배열과 연결 리스트

배열	연결 리스트
random access 가능	random access 불가능
배열 n번째 원소 접근 O(1)시간	리스트의 n번째 노드 접근시 O(n)시간 소요
원소 삽입&삭제 O(n) 시간 소요	원소 삽입&삭제가 배열보다 빠름

연결 리스트의 종류

1. 단일 연결 리스트(singly linked list)

각 노드 당 한개의 포인터가 있고 포인터는 다음 노드의 위치를 가르킨다.
테일에는 null이 들어간다.

2. 이중 연결 리스트 (Doubly linked list)

<출처> programiz

포인터를 두개 가지고 있어 이전노드와 다음 노드를 가리킨다.
데이터의 구조와 흐름이 복잡해질 수 있다.
이전 데이터의 주소도 가지고 있다.

3. 원형 연결 리스트 (Circular linked list)

<출처> programiz

단일 연결 리스트의 tail 노드가 head노드를 가리킨다.

💻 연결리스트 구현 방법

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');
...