배열과 연결리스트

🤓오늘의 공부 주제: 배열과 연결리스트🤓

배열

배열이란?
배열(array)또는 순차 리스트(sequential list)는 인덱스와 값의 쌍으로 이루어진 연속적인 메모리 위치의 집합이다.

배열을 위해서는 운영체제가 연속된 공간을 할당한다.
배열의 시작 주소만 알면 인덱스로 시작 주소 + 1이런 식으로 값을 찾아낸다. 따라서 읽기, 쓰기와 같은 참조에는 0(1)의 성능을 가진다.

단점은 크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다. 데이터 삽입, 삭제가 비효율적이다.

자바스크립트에서는 배열이 연속된 공간이 아니라 각기 다른 공간을 연결시켜서 연속된 공간처럼 보이게 만든다.

연결리스트

연결리스트란?
노드가 기본 구조. 노드는 데이터와 다음 데이터를 가리키는 변수 하나를 가짐. 이런 구조 때문에 연결 리스트라함.

배열의 단점을 해결하기 위해서는 메모리의 분산된 공간에 데이터를 할당하고 이를 연결해주면 됨.

장점: 배열의 초기 크기를 몰라도 됨. 오버헤드 없음(데이터를 뒤로 밀거나 땡길 필요 없음).

단점: 데이터에 바로 접근 불가. 노드들을 참조해서 값을 찾아야해서 시간복잡도 0(n)

💡요약 정리💡
배열: 크기 고정. 주소 연속. 데이터 참조 0(1). 삽입과 삭제0(n)

연결리스트: 크기 동적. 주소 불연속(힙메모리). 데이터 참조 0(n). 삽입과 삭제0(n)

	class Node{
    //생성자
    constructor(data, next = null){
      	//데이터는 값. next는 다음 데이터를 가리킴.
        this.data = data;
        this.next = next;
    }
}

class LinkedList{
    constructor(){
        this.head = null;
        this.count = 0;
    }
	//연결리스트의 모든 데이터 출력
    printAll(){
        let currentNode = this.head;
        let text = "[";
		
      	//현재 가리키는 노드가 null이 아닐때까지 = 연결리스트의 끝까지
        while(currentNode != null){
            text += currentNode.data;
            currentNode = currentNode.next;

            if(currentNode != null){
                text += ", ";
            }
        }

        text += "]";
        console.log(text);
    }

    clear(){
        this.head = null;
        this.count = 0;
    }
	
  	//원하는 인덱스에 데이터 삽입
    insertAt(index, data){
      	//인덱스가 데이터의 총개수보다 크거나 0보다 작으면 오류
        if(index > this.count || index < 0){
            throw new Error("범위를 넘어갔습니다.");
        }

        let newNode = new Node(data);
		
      	//맨 처음에 삽입할 경우
        if(index == 0){
          	//현재 헤드를 삽입할 노드의 다음 노드로 한칸 미루기
            newNode.next = this.head;
          	//새 노드를 헤드로 만들기
            this.head = newNode;
        // 중간에 삽입할 경우
        } else {
            let currentNode = this.head;
			
          	//삽입하고 싶은 인덱스보다 한칸 앞에서 멈추기
            for(let i = 0; i < index - 1; i++){
                currentNode = currentNode.next;
            }
          	//현재 노드(목표 인덱스-1)의 다음 노드인 목표 인덱스 노드를 새 노드의 다음 노드로 지정. = 새 노드의 다음 노드를 목표 인덱스로 지정.
            newNode.next = currentNode.next;
          	//현재 노드의 다음 노드를 새 노드로 지정
            currentNode.next = newNode;
        }
        this.count++;
    }
	
  	//마지막에 삽입하는 경우
    insertLast(data){
        this.insertAt(this.count, data);
    }
	
  	//특정 인덱스 노드 삭제하는 경우
    deleteAt(index){
      	//인덱스가 전체 데이터 개수보다 크거나 0 보다 작으면 오류
        if(index >= this.count || index < 0){
            throw new Error("제거할 수 없습니다.");
        }

        let currentNode = this.head;
		
      	//맨 처음 노드 지울 경우
        if(index == 0){
          	//삭제할 노드 저장해두기
            let deletedNode = this.head;
          	//헤드를 하나 뒤로 미루면 됨
            this.head = this.head.next;
            this.count--;
            return deletedNode;
        // 중간 노드를 지울 경우
        } else {
            for(let i = 0; i < index - 1; i++){
                currentNode = currentNode.next;
            }
			
          	// 삭제할 노드보다 하나 앞으로 와서 현재 노드 다음 노드를 저장
            let deletedNode = currentNode.next;
          	//현재 노드의 다음 노드를 현재 노드 다음다음 노드로 지정
            currentNode.next = currentNode.next.next;
            this.count--;
            return deletedNode;
        }
    }
	
  	//마지막 노드 지우기
    deleteLast(){
        return this.deleteAt(this.count - 1);
    }

  	//특정 인덱스 노드 추적하기
    getNodeAt(index){
        if(index >= this.count || index < 0){
            throw new Error("범위를 넘어갔습니다.");
        }

        let currentNode = this.head;
        for(let i = 0; i < index; i++){
            currentNode = currentNode.next;
        }

        return currentNode;
    }
}

export { Node, LinkedList };