전단 알고리즘 학습 (一) --- 선형 데이터 구조

배열
특성:
1. 물리 적 공간 에 연속 저장
2. 밑 에 있 는 배열 의 길 이 는 가 변 적 이지 않 습 니 다. js 에서 배열 의 길 이 를 바 꾸 면 성능 이 많이 소 모 됩 니 다.
3. 배열 의 변 수 는 배열 의 첫 번 째 요소 의 위치 (메모리 공간의 주소) 를 가리킨다.
장점: 조회 성능 이 좋다.어떤 위 치 를 조회 할 지 지정 합 니 다.
단점:
1. 공간 은 반드시 연속 되 어야 하기 때문에 배열 이 비교적 크 면 시스템 의 공간 파편 이 비교적 많 을 때 저장 하지 못 하기 쉽다.
2. 배열 의 길이 가 고정 되 어 있 기 때문에 배열 의 내용 을 추가 하고 삭제 하기 어렵다.
주의:
배열 a = [1, 2, 3, 4] 에서 a [0], a [1], a [2] 의 괄호 는 저장 주소 의 오프셋 을 나타 내 고 오프셋 을 통 해 데이터 성능 을 조회 하 는 것 이 가장 좋다.

var a = [1,2,3,4]; //              
var b = new Array(10); //           ，      

체인 테이블
특성:
1. 공간 적 으로 연속 이 아니다
2. 값 을 저장 할 때마다 인용 공간 을 하나 더 써 야 합 니 다.
장점:
1. 메모리 만 충분 하면 저장 할 수 있 으 니 공간 파편 문 제 는 걱정 하지 마 세 요.
2. 링크 의 추가 와 삭제 가 매우 쉽다
단점:
1. 조회 속도 가 느리다 (위치 조회)
2. 링크 의 모든 노드 는 종이 상자 next 의 인용 을 만 들 고 공간 을 낭비 해 야 합 니 다. 노드 안의 데이터 가 많 을 수록 이 부분 은 많이 사용 하 는 메모리 의 영향 이 적 습 니 다.

    function Node(value) {
        this.value = value;
        this.next = null;
    }
    var a = new Node(1);
    var b = new Node(2);
    var c = new Node(3);
    a.next = b;
    b.next = c;

반복 되 지 않 음

   //     
    var arr = [1, 2, 3, 4];

    function iterator(arr) {
        if (arr == null) return;
        for (var i = 0; i < arr.length; i++) {
            console.log(arr[i])
        }
    }

    iterator(arr);

    //      
    function Node(value) {
        this.value = value;
        this.next = null;
    }

    var a = new Node(1);
    var b = new Node(2);
    var c = new Node(3);
    var d = new Node(4);
    a.next = b;
    b.next = c;
    c.next = d;

    function iterator2(head) {
        var temp = head;
        while (true) {
            if (temp != null) {
                console.log(temp.value);
            } else {
                break;
            }
            temp = temp.next;
        }
    }

    iterator2(a);

차례로 옮 겨 다니다.

//     
var arr = [1, 2, 3, 4];

function iterator(arr, i) {
    if (arr == null || arr.length <= i) return;
    console.log(arr[i]);
    iterator(arr, i + 1);
}

iterator(arr, 0);

//      
function Node(value) {
    this.value = value;
    this.next = null;
}

var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);
a.next = b;
b.next = c;
c.next = d;

function iterator2(head) {
    if (head == null) return;
    console.log(head.value);
    iterator2(head.next);
}

iterator2(a);

링크 의 역 치

//      
function Node(value) {
    this.value = value;
    this.next = null;
}

var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);
a.next = b;
b.next = c;
c.next = d;

function reverse(head) {
    if (head.next.next == null) {
        head.next.next = head;
        return head.next;
    } else {
        var result = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }
}

function iterator2(head) {
    if (head == null) return;
    console.log(head.value);
    iterator2(head.next);
}

var newNode = reverse(a);

iterator2(newNode);

양 방향 링크

//      
function Node(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
}

var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);

a.next = b;
b.prev = a;
b.next = c;
c.prev = b;
c.next = d;
d.prev = c;