[5] [알고리즘 - 자료구조] 연결리스트(Linked List)란? (선형구조) javascript 구현

연결리스트

 

각 노드가 데이터와 포인터를 가지고

한 줄로 연결되어 있는 방식으로

데이터를 저장하는 자료 구조입니다.

 

좀 더 쉽게 알아보겠습니다.

 

데이터와

다음 순서의 주소 값을 가지고

하나의 덩어리를 '노드'라고 표현합니다.표현합니다.

 

이런 모양이 되겠네요.

 

 

이런 식으로 데이터가 연결되어 있는 것이 연결 리스트입니다.

가장 처음의 노드는 Head라고 부르고,

마지막 노드를 Tail 이라고도 부른다고 합니다.

 

 

만약 이러한 연결 리스트에서

데이터를 삭제하고자 한다면

이처럼 다음 주소 값을 변경해주고

하나의 노드만 삭제를 하면 됩니다.

 

배열에 비해 빠른 속도의 처리가 가능합니다.

따라서 삽입, 삭제 속도가 빠릅니다.

 

하지만

빠른 탐색이 가능했던 배열에 비해

연결 리스트는 탐색이 느리다는 단점이 있습니다.

 

4번째 데이터를 탐색할 때

배열은 바로 4번째 데이터를 찾아오는 반면에

연결 리스트는 Head에서 시작하여,

1번째로 이동후,

그다음 주소 값을 참조해 이동후

2번째의 데이터까지 찾고,

3번째, 4번째 이런 식으로

거쳐야 하기 때문에

탐색이 느리다는 단점이 있습니다.

 

다음 시간에 좀 더 자세하게

이유를 설명하도록 할게요.

 

지금까지 본 형태의 연결 리스트가

가장 기본 형태인

단일 연결 리스트입니다.

 

 

위 사진처럼

다음, 이전 2개의 주소 값을 가진 형태의

이중 연결 리스트,

 

마지막 노드를 첫 번째 노드로 연결된

원형 연결 리스트가 있습니다.

 

그러면 연결 리스트를

Javascript로 구현해보겠습니다.

 

/* 노드 */
class Node {
    constructor(data, nextNode = null) {
        this.data = data; // 데이터
        this.nextNode = nextNode; // 연결된 노드
    }
}

먼저 노드의 모양을 만들어주었습니다.

데이터와, 연결된 다음 노드가 담긴 nextNode.

 

 

class LinkedList {
    #head; // 연결 리스트 헤드
    #size; // 연결 리스트 총 길이

    constructor() {
        this.#head = null;  // 초기화
        this.#size = 0;     // 초기화
    }

    // 첫 번째 위치로 삽입
    insertFirst(data) {
        const node = new Node(data, this.#head);  // 노드 생성 (데이터, 현재 헤드를 다음 노드로 연결)
        this.#head = node;                        // 첫 노드 헤드에 위치
        this.#size++;                             // 총 개수 증가
    }

    // 연결 리스트 확인
    log() {
        console.log('head', this.#head);
        console.log('size', this.#size);
        return this.#head;
    }

    // 연결 리스트의 전체 데이타 확인
    printLinkedListValue() {
        let current = this.#head;
        while(current) {
            console.log(`data[${count}]=`, current.data);
            current = current.nextNode;
            count++;
        }
    }
}

 

일단, 가장 간단하게 만들 수 있는

첫 번째 헤드 위치로 데이터를 넣는

기능을 만들어주었으며,

로그를 찍어보도록

만들어주었습니다.

 

 

const linkedList = new LinkedList();

linkedList.insertFirst('4');
linkedList.insertFirst('3');
linkedList.insertFirst('2');
linkedList.insertFirst('1');

linkedList.log();
// "linkedList": {"data": "1","nextNode": {"data": "2","nextNode": {"data": "3","nextNode": {"data": "4","nextNode": null}}}}
linkedList.printLinkedListValue();
// data[0]= 1
// data[1]= 2
// data[2]= 3
// data[3]= 4

 

한번 여러분도 12F 눌러서

바로 실행해보세요!

 

그럼 이어서,

마지막 위치로 데이터 삽입,

원하는 위치에 데이터 삽입,

데이터 삭제,

해당 위치의 데이터 값 확인,

모두 초기화 기능을

각각 차례대로 만들어주겠습니다.

 

class LinkedList {
    #head; // 연결 리스트 헤드
    #size; // 연결 리스트 총 길이

    constructor() {
        this.#head = null;  // 초기화
        this.#size = 0;     // 초기화
    }

    // 첫 번째 위치로 삽입
    insertFirst(data) {
        const node = new Node(data, this.#head);  // 노드 생성 (데이터, 현재 헤드를 다음 노드로 연결)
        this.#head = node;                        // 첫 노드 헤드에 위치
        this.#size++;                             // 총 개수 증가
    }

    // 연결 리스트 확인
    log() {
        console.log('head', this.#head);
        console.log('size', this.#size);
        return this.#head;
    }

    // 연결 리스트의 전체 데이타 확인
    printLinkedListValue() {
        let current = this.#head;
        let count = 0;
        while(current) {
            console.log(`data[${count}]=`, current.data);
            current = current.nextNode;
            count++;
        }
    }

    // 마지막 위치에 데이터 삽입
    insertLast(data) {
        let node = new Node(data); // 노드 생성
        
        if(!this.#head) this.#head = node; // 현재 리스트에 값이 하나도 없을 경우, 헤드 위치에 바로 노드 연결.
        else {

            // 순차적으로 마지막 위치로 이동
            let current = this.#head; 
            while(current.nextNode) { // 연결된 노드 값이 없을 경우 반복문 중단.
                current = current.nextNode; // 반복하면서 연결된 리스트의 다음 노드 값으로 변경.
            }
            
            current.nextNode = node; // 마지막 다음 노드 값에 노드 삽입
        }

        this.#size++;  // 길이 증가
    }
    
    // 원하는 위치에 데이터 삽입
    insertAt (data, no) {

        // 범위가 벗어나는 위치 일 경우, 삽입이 안되거나, 마지막 위치에 삽입하거나 택 1
        // if(no > 0 && no > this.#size) return;
        if(no < 0) return;
        if(no > 0 && no > this.#size) return this.insertLast(data);

        // 첫 번째 위치일 경우 첫번째 삽입 함수 실행
        if(no === 0) return this.insertFirst(data);

        const node = new Node(data); // 노드 생성
        let current = this.#head; // 현재 위치의 노드
        let previous; // 이전 위치의 노드
        let count = 0;  // 현재 위치

        // 원하는 위치 바로 이전까지 탐색
        while(count < no) {
            previous = current; // 이전 위치 설정
            count++;
            current = current.nextNode; // 현재 위치 설정
        }

        node.nextNode = current; // 현재 위치를 삽입하는 노드 다음위치로 연결
        previous.nextNode = node; // 이전 노드의 연결된 노드 값을 새로 생성한 노드로 연결

        this.#size++; // 총 길이 증가
    }

    // 데이터 삭제
    removeData(no) {
        // 범위가 초과하는 경우는 처리X
        if(no < 0 || (no > 0 && no > this.#size)) return;
        let current = this.#head; // 현재 위치의 노드
        let previous; // 이전 위치의 노드
        let count = 0; // 현재 위치

        if(no === 0) this.#head = current.nextNode; // 첫 번째 데이터 삭제 시, 다음 노드를 헤드 위치로 변경
        else {
            // 순차적으로 탐색하여 해당 위치로 이동
            while(count < no) {
                count++;
                previous = current;
                current = current.nextNode;
            }

            // 이전 노드의 다음 연결 노드 값을 현재 위치의 다음 노드 값으로 연결
            previous.nextNode = current.nextNode;
        }

        this.#size--; // 길이 감소
    }

    // 리스트 초기화
    clear() {
        this.#head = null;
        this.#size = 0;
    }

    // 원하는 위치의 데이터 확인
    getData(no) {
        let current = this.#head;
        let count = 0;

        while (current) {
            // 원하는 위치의 데이터 리턴
            if(count === no) return current.data;
            count++;
            current = current.nextNode;
        }
    }
}

 

하나씩 천천히 만들어보고

직접 한번 만들어 봅시다!!

 

    const linkedList = new LinkedList();

    linkedList.insertFirst('1. 바나나');
    linkedList.insertLast('2. 사과');
    linkedList.insertLast('3. 딸기');
    linkedList.insertLast('4. 수박');
    linkedList.insertLast('5. 참외');
    console.log('getData==', linkedList.getData(2));
    linkedList.removeData(2);
    linkedList.insertAt("3. 복숭아", 2);

    const data = linkedList.log();
    linkedList.printLinkedListValue();

하나씩 실행해보며 테스트해봅시다!

중간에 딸기를 제거하고

복숭아로 넣어주는 것까지

모두 확인하셨나요!?

 

 

[6] [알고리즘 - 자료구조] 스택(Stack)이란? (선형구조) javascript 구현