(Javascript) [자료구조] List(1)

List

• 인덱스가 없이 빈틈없는 데이터를 적재한 배열
• 배열이 가지고 있는 인덱스라는 장점 대신 빈틈없는 데이터의 적재라는 점이 있는 자료구조
• 핵심은 엘리먼트들 간의 순서. 순서가 있는 데이터의 모임. 빈 엘리먼트를 허용하지 않는다
• 처음과 끝, 그리고 중간 엘리먼트까지 추가 및 삭제 가능
• 리스트에 데이터가 존재하는지 확인하는 기능
• 리스트의 모든 데이터에 접근할 수 있는 기능
• 종류
  1. 단일 연결 리스트 (Single Linked List) : 리스트를 이루고 있는 노드 하나에 해당 노드의 값과 다음 노드에 대한 주소를 포함. 하지만 이전 노드에 대한 정보는 갖고 있지 않고 다음 노드로만 이동할 수 있다
  2. 이중 연결 리스트 (Double Linked List) : 리스트를 이루고 있는 노드 하나에 해당 노드의 값과 다음 노드에 대한 주소, 그리고 자신의 이전 노드에 대한 주소도 갖게 된다. 이에 자신의 다음 노드와 이전 노드로의 이동이 수월
  3. 원형 연결 리스트 (Circular Linked List) : 마지막 노드가 처음 노드를 가리키는 연결 리스트

 

1. 단일 연결 리스트

function SingleNode(data) {
	this.data = data;
	this.next = undefined;
}
function SingleList() {
	this.head = undefined;
	this.tail = undefined;
	this.size = 0;
}
SingleList.prototype.insert = function (data) {
	if (!this.head) {
		this.head = new SingleNode(data);
		this.tail = this.head;
	} else {
		const temp = new SingleNode(data);
		this.tail.next = temp;
		this.tail = temp;
	}
	return ++this.size;
};
SingleList.prototype.remove() = function (data){
	if(!this.head) return;
	if(this.head.data == data) {
		const temp = this.head.next;
		delete this.head;
		this.head = temp;
		this.size--;
		return;
}
let curr = this.head;
while(curr != this.tail){
		if(!curr.next) return;
		if(curr.next.data === data){
			const temp = curr.next.next;
			delete curr.next;
			curr.next = temp;
			this.size--;
			return;
		}
		curr = curr.next;
	}
}
SingleList.prototype.contains() = function (data){
	let curr = this.head;
	if(curr.data===data) return true;
	while(curr != this.tail){
			if(curr.next.data === data){
			return true;
		}
		curr = curr.next;
		}
	return false;
};

Insert 메서드

• SingList.prototype.insert = function (data) {} : insert 메서드를 prototype에 메서드로 추가한다.
• if(!this.head) : 현재 헤드가 없으면 즉, 리스트가 하나도 없다면
• this.head = new SingleNode(data); : 리스트노드에 새롭게 하나를 추가한다.
• this.tail = this.head; 현재 꼬리도 현재 헤드라고 정의한다.
• else { const temp = new SingleNode(data); 현재 헤드가 있다면, 즉 노드가 하나 있으면 임시 temp에 새로운 노드를 생성한다.
• this.tail.next = temp; : 새롭게 만든 temp는 현재꼬리의 다음이다
• this.tail = temp; 현재 꼬리는 temp로 재정의한다
• ++return size; : 리스트의 크기를 +1 해준다.

remove 메서드

• SingleList.prototype.remove() = function (data) {} : remove 메서드를 prototype에 메서드로 추가한다.
• if(this.head.data == data ) {} : 지울 데이터가 현재 헤드의 데이터와 같다면
• const temp = this.head.next; : 현재 헤드의 다음 노드를 임시 변수 temp에 초기화한다
• delete this.head; : 현재 헤드를 삭제한다
• this.head = temp; : 임시변수 temp를 현재 헤드에 재정의 해준다.
• this.size--; : 리스트의 크기를 하나 줄여준다.
• let curr = this.head; curr이라는 변수를 현재 헤드로 초기화해준다. 여기서 curr 변수를 기준으로 하나씩 비교하여 지울 데이터를 찾아 준다
• while(curr != this.tail) {} : 변수 curr이 현재 꼬리가 될 때까지 반복하여 지울 데이터를 찾아 준다

contains 메서드

• SingleList.prototype.contains() = function (data) {} :contains 메서드를 prototype에 메서드로 추가한다.
• let curr = this.head; : 마찬가지로 현재 헤드를 curr이라는 변수로 초기화하여 기준을 잡아준다
• if(curr.data === data) : 지울 데이터가 curr의 데이터와 같으면 true라는 bool값을 넘겨준다
• while(curr != this.tail) {} : 기준인 curr 변수가 현재 꼬리랑 같을 때까지 반복
• curr = curr.next : 현재 curr의 다음으로 기준을 바꿔준다