2. 배열과 연결 리스트

배열은 기본으로 제공하는 자료구조

배열을 선언할 때 배열의 크기를 알려준다.

OS는 메모리에 연속되는 공간을 할당해준다.

OS는 배열의 시작 주소를 알기 때문에 상대 좌표로 값을 가져 올 수 있다.

배열의 인덱스 참조는 길이에 관계없이 한번에 가져오기 때문에 O(1)의 성능을 가지고 있다.

때문에 배열은 읽기/쓰기, 즉 참조에 좋은 성능을 보인다.

하지만 데이터 삽입, 삭제의 성능은 좋지 않다.

배열이 할당된 공간을 초과하게 되면 OS는 다시 연속되는 메모리 공간을 찾아서 배열을 복사해야 한다.

미리 많은 공간을 할당하여 배열을 사용할 경우 일시적으로 빨라지지만 그 이상의 공간이 필요하면 더 많은 시간이 그 공간보다 적게 사용한다면 메모리 낭비가 일어난다.

JS의 경우 배열을 사용할 때 크기를 지정하지 않는다. 상황에 따라 연속적 비 연속적으로 메모리 임의의 공간을 내부에서 배열처럼 사용한다.

연결 리스트

배열의 단점을 보완하기 위해 저장하려는 데이터를 메모리 공간에 분산하고 서로 연결하여 사용한다.

노드라는 것을 만들어 사용하는데 노드에는 데이터와 다음 노드를 가리키는 변수 하나를 가지고 있다.

연결 리스트는 첫 노드의 주소만 알고 있다면 다른 연결된 노드에 접근 할 수 있고 데이터 입력, 삭제 시

가리키는 노드의 변수 만 변경하면 된다.

데이터 접근 시 순차적으로 접근하여 O(n)의 성능을 가진다.

데이터의 수가 자주 바뀌지 않고 참조가 많이 일어난다면 배열을 데이터의 수가 자주 바뀐다면 연결 리스트를 사용한다.

연결리스트 구현

추상 자료형

• 어떠한 데이터(옷)와 그 데이터에 대한 연산(세탁기 기능)을 표기
• 데이터와 데이터를 처리하는 연산을 나열 하는것

추상 자료형을 기반으로 아래와 같이 코드 구현

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

class LinkedList {
	constructor() {
		this.head = null;
		this.count = 0;
	}
	printAll() {
		let currentNode = this.head;
		let text = '[';

		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) {
		if (index > this.count || index < 0) { // 예외 처
			throw new Error('범위가 넘어갔습니다.');
		}
		let newNode = new Node(data); // 삽입할 노드 생성

		if (index == 0) { // 리스트 맨 앞에 삽입하는 경우
			newNode.next = this.head;// 새로 생성한 노드의 next가 head를 가리키게 한다.
			this.head = newNode; // 새로 생성한 노드를 head로 변경해준다.
		} else { // 그외 경우에 삽입하는 경우
			let currentNode = this.head; // 삽입하려는 노드 바로 전까지 가기위한 
			//변수 생성 head에서 시작하기 때문에 head로 초기화
			for (let i = 0; i < index - 1; i++) { //목표 인덱스 바로전까지 next를 이용해 
				currentNode = currentNode.next;// currentNode를 이동
			}
			newNode.next = currentNode.next;//새로운 노드가 currentNode의 next를 가리킨다.
			currentNode.next = newNode;// currentNode가 새로운 노드를 가리킨다.
		}
		this.count++;
	}

	insertLast(data) {
		this.insertAt(this.count, data);
	}

	deleteAt(index) {
		if (index >= this.count || index < 0) {
			throw new Error('제거할 수 없습니다.');
		}
		let currentNode = this.head;

		if (index == 0) {
			let deleteNode = this.head;//삭제된 노드를 리턴하기위해 삭제될 노드를 저장한다.
			this.head = this.head.next;//그리고 head를 head의 next 노드로 설정해준다.
			this.count--;
			return deleteNode;
		} else {
			for (let i = 0; i < index - 1; i++) {
				currentNode = currentNode.next;
			}
			let deleteNode = currentNode.next;
			currentNode.next = currentNode.next.next;
			this.count--;
			return deleteNode;
		}
	}
	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 };

자바클래스 Node와 LinkedList를 import하여 테스트에 사용할 수 있다.

import { Node, LinkedList } from './LinkedList.mjs';

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);

node1.next = node2;
node2.next = node3;

console.log(node1.data);
console.log(node1.next.data);
console.log(node1.next.next.data);

let list = new LinkedList();

console.log('===== insterAt() 다섯번 호출 함 =====');
list.insertAt(0, 0);
list.insertAt(1, 1);
list.insertAt(2, 2);
list.insertAt(3, 3);
list.insertAt(4, 4);
list.printAll();

console.log('===== clear() 호출 함 =====');
list.clear();
list.printAll();

console.log('===== insterLast() 호출 함 =====');
list.insertLast(0);
list.insertLast(1);
list.insertLast(2);
list.printAll();

console.log('===== deleteAt() 호출 함 =====');
list.deleteAt(0);
list.printAll();
list.deleteAt(1);
list.printAll();

console.log('===== deleteLast() 호출 함 =====');
list.insertLast(5);
list.deleteLast();
list.deleteLast();
list.printAll();

console.log('===== getNodeAt() 호출 함 =====');
list.insertLast(1);
list.insertLast(2);
list.insertLast(3);
list.insertLast(4);
list.insertLast(5);
let secondNode = list.getNodeAt(2);
console.log(secondNode);

결과는 아래와 같다.

1
2
3
===== insterAt() 다섯번 호출 함 =====
[0,1,2,3,4]
===== clear() 호출 함 =====
[]
===== insterLast() 호출 함 =====
[0,1,2]
===== deleteAt() 호출 함 =====
[1,2]
[1]
===== deleteLast() 호출 함 =====
[]
===== getNodeAt() 호출 함 =====
Node {
  data: 3,
  next: Node { data: 4, next: Node { data: 5, next: null } }
}