자료구조와 알고리즘

[JS] 연결 리스트

AgileJung 2022. 8. 9. 21:43
728x90
반응형

추가와 삭제가 반복된다면 연결 리스트를 사용하자

 

연결 리스트란?

각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다.

각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

 

 

데이터 필드 = 데이터 영역 = 데이터 저장

링크 필드 = 포인터 영역 = 다른 노드의 주소 값을 저장

 

특징

  • 메모리가 허용하는 한 요소를 제한 없이 추가할 수 있다.

 

배열과 차이점

1. 메모리 차이

 

배열은 순차적인 데이터, 즉 메모리 영역이 연속적으로 사용된다.

연결 리스트는 각 데이터가 퍼져있다. 즉, 포인터를 사용하여 각 영역을 참조한다.

 

2. 요소 삭제 / 추가

배열

배열은 O(n) 시간 소요

 

연결 리스트

삭제

1. 삭제하려고 하는 요소를 지정

2. 삭제하려고 하는 요소의 전 요소의 포인터를 삭제하려고 하는 요소의 다음 요소에 연결

3. O(I) 시간 소요

 

추가

1. 추가할 요소를 포인터를 끼워놓을 부분의 다음 요소를 가리키게 함.

2. 끼워 넣을 영역 이전의 요소를 추가할 요소를 가리킨다.

3. O(I) 시간 소요

 

연결 리스트의 종류

연결 리스트는 단일 연결 리스트, 이중 연결 리스트, 환영 연결 리스트가 있다.

단일 연결 리스트

Singly Linked List

Head에서 Tail까지 단방향으로 이어지는 연결 리스트로 가장 단순한 연결 리스트다.

Head는 가장 첫 번째 요소, Tail은 가장 마지막 요소를 뜻한다. 포인터 영역이 NULL값이면 가장 끝이다.

 

 

단일 연결 리스트

요소 찾기

1. 헤드 포인터에서 시작

2. 다음 요소인 헤드를 찾는다.

3. 찾는 값이 아니라면 포인터를 통해 다음 요소로 넘어간다.

4. 찾는 값이라면 결과 값을 반환한다.

 

요소 추가

1. 추가할 요소의 포인터 영역을 추가할 영역의 다음 값의 데이터 영역을 가리키게 한다

2. 추가할 전의 요소의 포인터 영역을 추가할 요소의 데이터 영역을 가리키게 한다.

 

요소 삭제

1. 삭제할 요소의 이전 요소를 삭제할 요소의 다음 요소를 가리키도록 한다.

2. 삭제할 요소를 지워준다.

 

이중 연결 리스트

Doubly Linked List

양방향으로 이어지는 연결 리스트

포인터가 두 개 존재한다. (다음, 이전)

단일 연결 리스트보다 자료구조의 크기가 조금 더 크다.

이중 연결 리스트에서 사용되는 노드의 형태

 

이중 연결 리스트

 

요소 추가

1. 추가할 요소의 다음을 4를 가리키게 한다.

2. 추가할 요소의 이전 요소의 다음을 추가할 요소를 가리킨다

3. 4의 이전을 추가할 요소를 가리킨다.

4. 추가할 요소의 이전을 2를 가리키도록 한다.

 

요소 삭제

1. 삭제할 요소의 이전 요소의 다음을 삭제할 요소의 다음 요소를 가리키도록 한다.

2. 삭제할 요소의 다음 요소의 이전을 삭제할 요소의 이전 요소를 가리키도록 한다.

3. 요소 삭제

 

 

원형 연결 리스트

Circular Linked List

List의 Tail이 Head로 연결되는 연결 리스트

중간에서 탐색을 시작해도 전체를 돌 수 있다.

원형 연결 리스트

 

 

자바스크립트로 연결 리스트를 구현해보자.

여기서 구현이라는 말은 자바스크립트를 이용하여 연결 리스트의 구조를 만들어 보겠다는 말이다.

노드

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

 

 

연결리스트에서 사용할 노드의 기본 정보를 설정했다.

this.value는 데이터 값을, this.next는 포인터를 말한다.

 

연결 리스트

단일 연결 리스트

class SinglyLinkedList{
	constructor() {
    	this.head = null;
        this.tail = null;
    }
    // 요소 찾기
    find(){}
    // 요소 삭제
    remove(){}
    // 요소 추가
    append(){}
    // 요소 끼워넣기
    insert(){}
}

단일 연결 리스트의 틀을 만들었다.

this.head와 this.tail은 각각 헤드 포인터, 테일포인터를 가리킨다. 

단일 연결 리스트 안에서 사용할 기능들(find(), remove(), append(), insert())도 연결 리스트 안에다가 같이 작성한다.

 

요소 찾기

find(value){
	let currNode = this.head;
    while(currNode.value !== value){
    // 원하는 값을 찾을 때까지 순회한다.
    // 값을 찾으면 해당 노드를 리턴한다.
    	currNode = currNode.next
    }
    return currNode;
}

 

요소 삭제

remove(value){
    let preNode = this.head;
    while(preNode.next.value !== value){
    	preNode = preNode.next;
    }
    if(preNode.next !== null){
    	preNode.next = preNode.next.next;
    }
}

요소 추가

append = 끝에

append(newValue){
    const newNode = new Node(newValue);
    if(this.head === null){
      this.head = newNode;
      this.tail = newNode;
    } else {
    	this.tail.next = newNode;
        this.tail = newNode;
    }
}

요소 끼워넣기

중간에 = insert

insert(node, newValue){
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
}

 

연결 리스트로 추가와 삭제가 반복되는 문제를 해결할 수 있으니 잘 이해해보자.

 

 

 

728x90
반응형