Linked List (연결리스트)란?

Linked List (연결 리스트)란?

연속된 노드(Node) 의 연결체이다.

연결리스트에서 Node란 무엇인가?

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

노드의(Node)의 구조는?

data: 노드가 담고 있는 데이터/값 next: 링크/포인터 역활, 다음 노드의 주소를 저장

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

연결리스트 (Linked List)의 구조는?

A의 노드의 next포인터가 B를 가리키고, B의 노드도 next포인터가 C를 가리키고, 마지막으로 C의 노드는 다음노드는 존재하지 않아서 null값을 가지게 된다.

이렇게 해서 하나의 연결리스트가 완성된다.

그리고 연결리스트의 시작부분에 있는 노드를 head라고 부른다.
연결리스트의 마지막부분은 tail이라고 부른다. 꼬리를 의미한다.

배열 vs 연결 리스트

배열은 모든 원소들이 이어진 메모리 공간에 자리 잡고 있다.
이것을 이용해서 배열의 인덱스를 이용하여 원소탐색을 효율적으로 빠르게 실행할 수 있게 도와준다.

반면

연결리스트는 하나의 노드들이 각자의 메모리공간 어딘가에 자리 잡고 있다.
이 처럼 이어진 메모리공간이 아닌 불특정한 공간에 존재하기 때문에
포인터또는 주소를 참조하는 필드를 통해서 연결을 시켜줘야한다.

그렇게 때문에 노드의 탐색은 선형 시간이 걸린다.

예를 들면

“c노드까지 가고싶다면”
a와 b노드를 필수적으로 거쳐야만 갈 수 있게 된다.

배열의 특징

1. 배열은 random access 가능

-> 배열의 한 원소를 방문할 때 index를 사용해서 상수시간으로 바로 접근이 가능하다.

2. 원소 삽입 & 삭제 일반적으로 O(n) 시간소요 = 리니어타임으로 처리할 수 있다.

-> O(n) 시간소요 = 리니어타임 = 알고리즘 입력크기에 비례하여 실행시간이 증가한다는 것이다.

연결리스트 특징

1. random access 불가능 -> 구조상 불가능하다.

예를 들어 리스트의 n번째 노드에 접근하려면 그 앞에 위치한 모든 노드들을 방문해야 되기 때문이다.
따라서 일반적으로 노드를 접근할 때는 리니어 타임이 걸린다. (선형 시간이 걸림)

배열보다 빨라질 수 있는 노드 삽입 & 삭제

구조상 장점으로 상황에 따른 노드의 삽입 또는 삭제가 배열에 비해 빨라질 수 있다.
예시로 연결리스트에 노드를 맨 앞에 삽입시켜 줄때는 head 노드의 참조위치만 바뀌는 것이기 때문에
이럴 경우에는 상수시간(conston time)이기 때문에 굉장히 빠른 속도로 처리가능하다.

연결 리스트의 종류

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

단일 연결리스트의 구조특징은 간단하다.
다음 노드에 대한 포인터들만 가지고 있고, 한쪽 방향으로만 흐르는 데이터 구조의 패턴이다.

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

이중 연결리스트의 특징은 다음 노드에 대한 포인터 뿐만이 아니라
이전 노드를 가리키는 포인터들도 가지고 있다.

앞뒤로 탐색하는게 빠르다는 장점이 있지만 노드마다 두개의 포인터를 관리해줘야되기 때문에
데이터의 구조와 흐름이 오히려 복잡해 질 수 있다.

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

일반적인 연결리스트에 마지막포인터가 가리키는 노드가 head노드를 가리키게 된다.
즉, tail노드가 head노드를 가리키는 구조가 원형 연결 리스트이다.

연결리스트 구현방법

연결리스트는 노드의 연결체이다.

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

사진과 같이 노드의 형태를 코드로 구현하면 이러한 형태가 만들어진다.
데이터필드와 링크 역할을 해주는 next필드도 같이 있는걸 볼 수 있다.

노드를 활용해서 연결리스트 구현

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. head.next.next = Node(“c”)는 새로 생성되는 노드c로 지정하여 연결시켜준다.
   
4. head.next.next.next = Node(“d”)는 노드c를 마지막으로 생성되는 노드d에 지정해준다.
   

이렇게 a, b, c, d 모든 노드들을 연결시켜주었다.

결과적으로 “ a-> b-> c-> d-> null” 이러한 연결리스트가 만들어진다.