따라서 연결된 목록에 대해 알려주세요.

최근 코딩 부트 캠프를 졸업 한 저는 기본적인 지식을 향상시키기 위해 데이터 구조와 알고리즘을 깊이 연구했습니다. 연결된 목록은 비교적 단순한 데이터 구조이지만 앞으로 나아가는 더 복잡한 데이터 구조의 기초입니다. 이 기사에서는 링크드리스트의 강점, 약점 및 구현 방법에 대해 설명합니다.

데이터 구조는 간단히 말해서 데이터를 효율적으로 구성하고 보관하는 방법입니다.

데이터 구조 란?

데이터 구조는 간단히 말해서 데이터를 효율적으로 구성하고 보관하는 방법입니다. 이를 통해 나중에 액세스 할 수 있도록 정보를 보유 할 수 있습니다. 특정 항목을 검색하거나 특정 순서를 갖도록 정렬하거나 대규모 데이터 세트를 관리 할 수도 있습니다. 자바 스크립트에는 여러분이 매우 익숙한 배열과 객체의 데이터 구조가 있습니다. 이들은 언어에 고유 한 기본 데이터 구조입니다. 기본이 아닌 데이터 구조는 프로그래머가 정의한 데이터 구조입니다. 예를 들면 스택, 큐, 트리, 그래프 및 해시 테이블이 있습니다.

연결된 목록이란 무엇입니까?

연결 목록은 요소를 순차적으로 보유하는 선형 데이터 구조입니다. 익숙한가요? 그것들은 배열과 유사하지만 완전히 동일하지는 않습니다. 배열은 인덱스0입니다 . 즉, 각 인덱스는 값에 매핑 되고 배열의 첫 번째 요소는 인덱스 0에서 시작합니다. 인덱스를 알고있는 한 배열에서 요소를 쉽게 가져올 수 있습니다.

반면에 연결된 목록은 다른 노드 를 가리키는 노드로 구성 됩니다. 각 노드는 자신과 다음 노드 만 알고 있습니다. 선형 데이터 구조로서 항목은 순서대로 정렬됩니다. 기차로 생각할 수 있습니다. 각 철도 차량은 다음 철도 차량에 연결되어 있습니다. 연결된 목록은 색인이 생성 되지 않으므로 5 번째 요소에 직접 액세스 할 수 없습니다. 5 번째 요소를 찾을 때까지 처음부터 시작하여 다음으로 이동하고 다음으로 이동해야합니다. 첫 번째 노드를 머리라고하고 마지막 노드를 꼬리라고합니다. 연결 목록에는 단일 연결 목록, 이중 연결 목록, 순환 연결 목록 등 다양한 유형이 있습니다. 이 기사에서는 단일 연결 목록에 초점을 맞출 것입니다.

배열 전체의 요소에 액세스하는 것이 더 쉽지만 비용이 발생합니다.

배열에 연결된 목록을 사용하는 이유는 무엇입니까?

궁금 할 것입니다.하지만 배열을 사용하여 요소에 직접 액세스 할 수 있다면 왜 이것을 사용합니까? 사실입니다! 배열 전체의 요소에 액세스하는 것이 더 쉽지만 비용이 발생합니다.

배열이되어 색인 - 당신은 처음이나 중간에서 요소를 제거해야 할 때마다 그래서, 모두 다음과 같은 지표가 이동 될 필요가있다. 요소를 삽입해야하는 경우에도 마찬가지입니다. 모든 다음 요소는 다시 색인화되어야합니다. 연결 목록에서 요소를 삽입하거나 제거 할 때 색인을 다시 생성 할 필요가 없습니다. 중요한 것은 가리키는 노드뿐입니다 .

단일 연결 목록 구현

연결 목록에는 단일, 이중 및 순환 등 다양한 유형이 있습니다. 단일 연결 목록은 각 노드에 값과 다음 노드에 대한 포인터가있는 연결 목록 유형입니다 (꼬리 노드 인 경우 null). 반면에 이중 연결 목록에는 이전 노드에 대한 추가 포인터가 있습니다. 순환 연결 목록은 꼬리 노드가 다시 헤드 노드를 가리키는 곳입니다.

참고 : 시각적 학습자 인 경우 VisuAlgo 는 놀면서 데이터 구조가 변경되는 것을 볼 수있는 좋은 장소입니다.

전체 코드를 건너 뛰려면이 GitHub 요점을 확인하세요 .

노드 생성

사용할 노드를 구축하는 것으로 시작하겠습니다. 값과 다음 포인터 를 갖게되며 , 이는 후속 이웃을 나타냅니다.

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

SinglyLinkedList라는 클래스를 작성하여 시작하여 목록의 머리, 꼬리 및 길이에 대한 기초를 제공합니다.

class SinglyLinkedList {    
      constructor() {        
          this.head = null;
          this.tail = null;
          this.length = 0;
      }
}

끝에 노드를 추가하기 위해 목록에 이미 선언 된 헤드가 있는지 확인합니다. 그렇지 않은 경우 머리와 꼬리를 새로 만든 노드로 설정합니다. head 속성이 이미있는 경우 tail의 다음 속성을 새 노드로 설정하고 tail 속성을 새 노드로 설정합니다. 길이를 1 씩 늘립니다.

push(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++;
        return this;
}

마지막에 노드를 제거하려면 먼저 목록에 노드가 있는지 확인해야합니다. 노드가 있으면 꼬리에 도달 할 때까지 목록을 반복해야합니다. 두 번째에서 마지막 노드까지의 다음 속성을 null로 설정하고 tail 속성을 해당 노드로 설정하고 길이를 1만큼 줄인 다음 제거 된 노드의 값을 반환합니다.

꼬리 노드 제거, 노드 77.

pop() {
        if (!this.head) return undefined;
        var current = this.head
        var newTail = current
        while (current.next) {
            newTail = current
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return current;
}

처음부터 노드를 제거하려면 목록에 노드가 있는지 확인합니다. 현재 헤드 속성을 변수에 저장하고 헤드를 현재 헤드의 다음 노드로 설정합니다. 길이를 1만큼 줄이고 제거 된 노드의 값을 반환합니다.

shift() {
        if (!this.head) return undefined
        var oldHead = this.head;
        this.head = oldHead.next;
        this.length--
        if (this.length===0) {
            this.head = null;
            this.tail = null;
        }
        return oldHead
}

처음에 노드를 추가하려면 먼저 노드를 만들고 목록에 head 속성이 있는지 확인합니다. 그렇다면 새로 생성 된 노드의 다음 속성을 현재 헤드로 설정하고 헤드를 새 노드로 설정 한 다음 길이를 늘립니다.

목록 시작 부분에 노드 61을 추가합니다.

unshift(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++
        return this
}

목록에서의 위치를 ​​기준으로 노드에 액세스하려면 먼저 인덱스가 유효한 인덱스인지 확인합니다. 그런 다음 카운터 변수를 유지하면서 목록을 반복합니다. 카운터 변수가 인덱스와 일치하면 찾은 노드를 반환합니다.

get(idx) {
        if (idx < 0 || idx >= this.length) return null
        var counter = 0;
        var current = this.head
        while (counter !== idx) {
            current = current.next;
            counter++;
        }
        return current;
}

위치에 따라 노드를 변경하려면 먼저 get 메소드를 사용하여 노드를 찾고 값을 새 값으로 설정합니다.

set(idx, val) {
        var foundNode = this.get(idx)
        if (foundNode) {
            foundNode.val = val
            return true;
        }
        return false;
}

노드를 삽입하려면 먼저 인덱스를 확인합니다. 0과 같으면 unshift 방법을 사용합니다. 길이와 같으면 목록에 넣습니다. 그렇지 않으면 인덱스보다 작은 get 메서드를 사용하여 before 노드를 얻습니다. 기본적으로 포인터가 올바른 노드로 향하도록하기 위해 선택한 인덱스 전후의 노드를 추적해야합니다.

목록의 위치 3에 노드 60을 삽입합니다.

insert(idx, val) {
        if (idx < 0 || idx > this.length) return false;
        if (idx === 0) {
            this.unshift(val)
            return true;
        };
        if (idx === this.length) {
            this.push(val);
            return true;
        };
        var newNode = new Node(val);
        var beforeNode = this.get(idx-1);
        var afterNode = beforeNode.next;
        beforeNode.next = newNode;
        newNode.next = afterNode;
        this.length++;
        return true;
}

위치를 기준으로 노드를 제거하려면 get 메서드를 다시 사용하고 노드 삽입에 사용한 것과 동일한 원칙을 사용합니다. 선택한 인덱스 이전의 노드를 추적하여 포인터를 조작 할 수 있습니다.

remove(idx) {
        if (idx < 0 || idx > this.length) return undefined;
        if (idx === this.length-1) {
            this.pop()
        }
        if (idx === 0) {
            this.shift()
        }
        var prevNode = this.get(idx-1)
        var removeNode = prevNode.next
        prevNode.next = removeNode.next
        this.length--;
        return removeNode;
}

연결 목록의 강점

연결 목록 사용의 이점은 요소를 빠르게 삽입하고 제거 할 수 있다는 것입니다. 연결 목록은 인덱싱되지 않기 때문에 요소 삽입이 비교적 빠르고 쉽습니다.

연결 목록의 끝에 추가 하려면 이전 꼬리가 새 노드를 가리키고 꼬리 속성이 새 노드로 설정되어야합니다. 연결 목록의 시작 부분에 추가하는 것은 동일한 전제이지만 새 노드는 이전 헤드를 가리키고 헤드 속성은 새 노드로 설정됩니다. 기본적으로 동일한 동작이므로 삽입은 O (1)입니다.

참고 : 연결 목록 중간에 삽입하려면 노드 (O (N))를 찾기 위해 검색 한 다음 노드 (O (1))를 삽입해야합니다.

연결 목록에서 노드를 제거 하는 것은 쉽지만 그렇지 않습니다. 이것은 어디에 달려 있습니다. 목록의 시작 부분에서 노드를 제거하는 것은 간단합니다. 두 번째 노드가 새 헤드가되고 이전 헤드의 다음 포인터를 null로 설정합니다. 전체 목록을 살펴보고 두 번째에서 마지막 노드까지 중지해야하므로 끝에서 제거하는 것이 더 까다 롭습니다. 최악의 경우 O (N), 최상의 경우 O (1).

연결된 목록의 약점

연결 목록의 약점은 재 인덱싱이 없기 때문에 발생합니다. 요소에 직접 액세스 할 수 없기 때문에 요소 검색 및 액세스가 더 어려워집니다.

연결 목록에서 노드를 검색하고 액세스 하려면 목록의 시작 부분에서 시작하여 목록 아래의 이동 경로를 따라야합니다. 목록의 끝에서 노드를 검색하는 경우 전체 연결 목록을 살펴야하므로 시간 복잡도를 O (N)으로 만들 수 있습니다. 목록이 커지면 작업 수가 늘어납니다. 랜덤 액세스가있는 배열과 비교하여 요소에 액세스하는 데 일정한 시간이 걸립니다.

그게 다야!

연결 목록은 처음에 삽입 및 삭제가 핵심 작업 인 경우 배열에 대한 훌륭한 대안입니다. 배열은 인덱싱되지만 연결 목록은 그렇지 않습니다. 연결된 목록은 스택과 대기열이 구축되는 기본 데이터 구조이기도합니다. 이에 대해서는 이후 기사에서 설명하겠습니다. 여기까지 하셨다면, 당신에게 찬사를 보내고 프로그래밍 여정과 함께 약간의 너겟을 배웠기를 바랍니다!

참고 문헌

JavaScript의 데이터 구조 연결 목록이란 무엇입니까? [1 부]

Suggested posts

JavaScript 테스트의 기초

JavaScript 테스트의 기초

"잠깐만 요, JavaScript 테스팅에 대한 또 다른 기사"라고 생각할 수 있습니다. 예, JavaScript 테스트의 기본 사항에 대해 더 많이 이야기하고 싶은 이유는이 주제에 대한 많은 기사가 JavaScript 테스트를 작성하기위한 코드 스 니펫과 도구를 보여줌으로써 매우 유사한 방식으로 작성 되었기 때문입니다.

Big-O 렌즈를 통한 Javascript의 배열 및 객체 성능

Big-O 렌즈를 통한 Javascript의 배열 및 객체 성능

프로그램의 효율성은 요소의 검색, 정렬, 액세스, 삽입 및 제거와 같은 작업을 수행하기 위해 엄청난 양의 데이터를 처리 할 때 시간 복잡성에 직접적으로 의존합니다. 성능 향상의 필요성에 따라 객체와 배열을 선택적으로 사용할 수 있습니다.

Related posts

성능 최적화 된 A / B 테스트 솔루션

성능 최적화 된 A / B 테스트 솔루션

의제 : 소개 : TL;하지만 읽을 수 있습니다. A / B 테스트, CloudFront 및 Lamba @ edge에 대해 이미 알고있는 경우 AWS Lambda @ edge를 사용한 A / B 테스트로 직접 이동하십시오. A / B 테스트 란 무엇입니까? A / B 테스트는 웹 사이트의 두 가지 버전에 대한 사용자의 참여를 비교하는 데 초점을 맞춘 UX 연구 방법론입니다.

fp-ts (Typescript)에서 Option 및 둘 중 하나 사용

저는 함수형 프로그래밍을 좋아합니다. 몇 년 동안 실수를하거나 토끼 구멍을 뚫는 것으로부터 저를 몇 번 구해 주었기 때문입니다. 동일한 입력이 주어지면 출력이 항상 동일하다는 것을 알면 안심입니다.

Syncfusion Blazor 파일 업로드 구성 요소에서 이미지를 미리 보는 방법

Syncfusion Blazor 파일 업로드 구성 요소에서 이미지를 미리 보는 방법

Syncfusion Blazor 파일 업로드는 하나 이상의 파일, 이미지, 문서, 오디오, 비디오 및 기타 파일을 서버에 업로드하기위한 구성 요소입니다. 여러 파일 선택, 진행률 표시 줄, 자동 업로드, 끌어서 놓기, 폴더 (디렉터리) 업로드, 파일을 포함하는 다양한 기능을 갖춘 HTML5 업로드 구성 요소 (<input type =”file”>)의 확장 버전입니다. 검증 등.

6 React 개발자로서 후회

내가 일찍했으면하는 것

6 React 개발자로서 후회

React는 배울 수있는 훌륭한 도구입니다. 그것은 우리가 우리 자신의 방식으로 일을 할 수있게합니다.