자료구조와 알고리즘 7장 단일 연결 리스트 (2)

TIL 날짜

2023.12.11

 

Contents

1. 연결 리스트 와 배열의 빅오 표기법
2. 연결 리스트 사용 케이스
3. Class를 이용한 단일 연결 리스트 메소드 활용방법 (2)

단일 연결 리스트의 빅오 표기법

연산	배열	연결 리스트
읽기(Read)	O(1)	O(N)
검색(Search)	O(1)	O(N)
삽입(Post)	O(N) (끝에서 부터 O(1))	O(N) (Head 시작 O(1))
삭제(Delete)	O(N) (끝에서 부터 O(1))	O(N) (Head 시작 O(1))

 

연결 리스트 사용 케이스

열차의 모습

상황: 기차에 좌석이 가득차 새로운 기차를 연결할려고 한다.과정1. 기차에 필요한 좌석이 몇석인지 확인한다.2. 기차를 얼마나 연결해야 하는지 확인한다.3. 기차에 뒤에 연결 고리를 만들어 앞 혹은 뒤에 기차랑 연결한다.4. 기차가 작동 되는지 확인하고 기차를 운행한다.결론: 기차에 좌석을 얼마나 연결을 해도 기차는 여전히 운행이 잘되고 있다. 예시

 

유명 맛집 웨이팅

상황: 현재 테이블이 손님들로 가득 차 있다.

과정 

1. 손님 4명이 같이 들어갈 좌석이 필요해 인터넷으로 예약을 해놓았다. (예약번호 지정)

2. 손님 2명이 같이 들어갈 좌석이 필요해 와서 예약을 했다. (예약 지정)

3. 2명이서 앉을수 있는 테이블이 좌석이 비어졌다.

4. 2의 손님들을 좌석에 앉힌다.

5. 1의 손님들은 계속 대기중이다.

결론: 1의 손님들은 순서가 밀렸지만 기다리고 있다는 사실은 변하지 않았다.

Class를 이용한 단일 연결 리스트 메소드 활용 방법 (2)

기본적인 툴 

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

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

 

1. Get 메소드

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

 

2. Set 메소드

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
	set(index.val){
	let foundNode = this.get(index);
	if(foundeNode){
	foundNode.val = val;
	return true;
	}
	return false;
     }
}

 

3. Insert 메소드

class SinglyLinkedList{
	insert(index,val){
	if(index < 0 || index >this.length) return false;
	if(index === this.length) return this.push(val);
	if(index === 0) return this.unshift(val);
	let newNode = new Node(val);
	let prev = this.get(index - 1); 
	let temp = prev.next;
	prev.next = newNode;
	newNode.next =temp;
	this.length++;
	return true;
}
}

 

4. remove 메소드

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
	remove(index){
	if(index <0 || index>=this.length) return undefined;
	if(index === 0) return this.shift();
	if(index === this.length -1) return this.pop();
	let previousNode = this.get(index - 1);
	let removed = previousNode.next
	previousNode.next = removed.next;
	this.length--
	return removed
}
}

 

5. reverse 메소드

class SinglyLinkedList{
	reverse(){
	let node = this.head;	
	this.head = this.tail;
	this.tail = node;
	let next;
	let prev = null;
	for(let i = 0; i<this.length; i++){
	next = node.next;
	node.next = prev;
	prev = node;
	node = next;
}	return this;
}}