[자료구조] 단일 연결 리스트(Singly Linked List)

1. 연결 리스트 소개

1-1. head, tail, length 프로퍼티를 담고 있는 자료 구조

• head = 연결 리스트의 시작 노드
• tail = 연결 리스트의 마지막 노드
• 중간 노드들은?
  • head 노드로 부터 다음 노드, 그 다음 노드, ...를 알아내는 방식으로 접근한다.
• length = 작업을 용이하게 하기 위해 길이를 유지한다.
  • 필요한 작업을 수행하기 위해 연결 리스트에 몇 개의 요소가 있는지 알아야 한다.

1-2. 연결 리스트는 노드로 구성되어 있고, 각 노드는 value와 포인터를 갖는다.

• 포인터는 다른 노드나 null을 가리킨다.
  • 포인터가 null을 가리킨다 ? = 더이상 다음 노드가 없다.

1-3. 단일 연결리스트란?

• 각 노드가 다음 노드로 오직 단일 방향으로만 연결되어 있는 연결 리스트
  

2. 배열과 연결 리스트의 차이점

2-1. 연결리스트는 엘리베이터가 없는 건물이고 배열은 엘리베이터가 있는 건물

2-2. 표 정리

리스트	배열
인덱스가 없다	순서대로 인덱스가 있다
next 포인터를 가진 노드를 통해 연결된다	삽입과 삭제에 비용이 많이 들 수 있다(expensive)
랜덤 액세스가 허용되지 않는다	특정 인덱스로 빠르게 접근할 수 있다

3. 단일 연결리스트 구현

// val  = 값
// next = 포인터

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

const first = new Node('Hi');
first.next = new Node('there');
first.next.next = new Node('how');
first.next.next.next = new Node('are');
first.next.next.next.next = new Node('you');

이 상태에서 first는 이렇게 생겼다. 두번째 사진은 next를 끝까지 펼친 모습이다.

3-1. next.next.next...는 너무 번거롭다. push 메서드 만들기

push 메서드 역할 = 새로운 Node를 연결 리스트의 끝에 추가

// 의사코드
// 1. push 메서드는 한 value을 받아야 한다.
// 2. 메서드에 전달되는 value를 사용해서 새로운 Node를 생성해라.
// 3. 리스트에 head가 없다면, head와 tail은 새로 생성한 Node가 되도록 설정해라.
// 3-1. 그게 아니면, tail의 다음 프로퍼티로 새로운 Node를 설정하고 tail 프로퍼티는 새롭게 생성된 Node가 되도록 해라.
// 4. 길이를 1 추가해라.
// 5. 연결 리스트를 반환해라.

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  
  push(val) {
    const newNode = new Node(val);
    
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    
    this.length++;
    
    return this;
  }
}

const list = new SinglyLinkedList();

list.push('단일');
list.push('연결');
list.push('리스트');

결과화면

• '연결'은 head의 next에 담겨있다.
  

3-2. pop 메서드 추가

// 의사코드
// 1. 리스트에 아무 노드도 없는 경우, undefined를 반환한다.
// 2. tail에 도달할 때까지 리스트를 순회한다.
// 3. 마지막에서 2번째 노드의 `next`를 `null`로 설정한다.
// 4. 마지막에서 2번째 노드를 tail로 설정한다.
// 5. 길이를 1 감소시킨다.
// 6. 제거된 노드의 값을 반환한다.

class SinglyLinkedList{
	constructor() {
    	this.head = null;
      	this.tail = null;
      	this.length = 0;
    }
  	
  	...
    
  	pop() {
    	if (!this.head) return undefined;
      
      	let current = this.head;
      	let newTail = current;
      	
      	while (current.next) {
        	newTail = current;
          	current = current.next;
        }
      
      	this.tail = newTail;
      	this.tail.next = null;
      	
      	this.length--;
        
        // length가 1일때 pop()을 실행할 경우 head와 tail이 같은 노드를 가리키기 때문에 초기화
      	if (this.length === 0) {
        	this.head = null;
          	this.tail = null;
        }
      
      	return current;
    }
}

const list = new SinglyLinkedList();

list.push('단일');
list.push('연결');
list.push('리스트');

결과화면

• pop 메서드를 실행하면 '리스트' 노드를 반환한다.
• list 변수에는 '리스트' 노드가 사라져 있고 새로운 tail로 '연결'이 설정되었다.

3-3. shift 메서드 추가

// 의사코드
// 1. 노드가 없을 경우, undefined를 반환한다.
// 1-1. 노드가 있을 경우, 현재의 head를 변수에 저장하고 
// 2. 현재 head의 next 노드를 가리키도록 헤드 속성을 업데이트한다.
// 3. 리스트의 길이를 1 감소시킨다.
// 4. 제거된 이전 head의 값을 반환한다.

...

shift() {
	if (!this.head) return undefined;
  	
  	let oldHead = this.head;
  	this.head = oldHead.next;
  
  	this.length--;
  
  	if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
  
  	return oldHead;
}

결과화면

3-4. unshift 메서드 추가

// 의사코드
// 1. 메서드로 전달된 값을 사용해서 새로운 노드를 생성한다.
// 2. list에 head가 없으면 head와 tail은 새롭게 생성된 노드가 되도록 한다.
// 2-1. 노드가 이미 있는 경우, 새롭게 생성된 노드의 next를 현재의 head 값으로 설정한다.
// 3. list의 길이를 1 증가시킨다.
// 4. liked list를 반환한다.

unshift(val) {
	const newNode = new Node(val);
  
  	if (!this.head) {
    	this.head = newNode;
      	this.tail = this.head;
    } else {
    	newNode.next = this.head;
  		this.head = newNode;
    }
  	
  	this.length++;
  
  	return this;
}

결과화면

3-5. get 메서드 추가

• 연결리스트 내에서 위치로(by it's position) 노드를 검색(retrieve)하는 메서드

// 의사코드
// 1. index를 받는다.
// 1-1. index가 음수이거나 리스트의 길이와 같거나 길이보다 클 경우 not working (return null)
// 2. 루프를 통해 인덱스가 지정하는 위치에 이를 때까지 반복해서 이동해서 해당 index 위치에 있는 노드를 반환한다.

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

결과

3-6. set 메서드 추가

• 연결리스트 내에서 그 위치에 따라 노드의 값을 바꾸는 메서드

// 1. index와 value 받기
// 2. get 메서드를 사용해서 노드 찾기
// 3. 노드가 없을 경우 return false
// 4. 노드가 있을 경우 그 노드의 값이 value가 되도록하고 return true

set(index, val) {
	const foundNode = this.get(index);
  	if (foundNode) {
    	foundNode.val = val;
      	return true;
    } else return false;
}

결과

---

(추가) Class의 Static(정적) 메서드 관련

강의에서 정적 메서드 내용이 지나갔는데 딥다이브에서 읽은 기억이 나서 찾아본 내용
MDN에서 정적 메서드는 애플리케이션 유틸리티 함수를 만드는데 사용된다고 한다.

class Student {
	constructor(firstName, lastName) {
    	this.firstName = firstName;
      	this.lastName = lastName;
    }
  	
  	// 클래스 몸체에서 정의한 메서드는 기본적으로 프로토타입 메서드가 된다
  	fullName() {
    	return `Your full name is ${this.firstName} ${this.lastName}`;
    }
  
  	// 정적 메서드
  	static enrollStudents(...students) {
    	return 'ENROLLING STUDENTS!';
    }
}

let firstStudent = new Student('Colt', 'Steele');
let secondStudent = new Student('Blue', 'Steele');

// 정적 메서드를 사용하면 클래스의 인스턴스화 없이 호출될 수 있다.
Student.enrollStudents([firstStudent, secondStudent]);

정적 메서드와 프로토타입 메서드의 차이점

• 정적 메서드와 프로토타입 메서드는 자신이 속해 있는 프로토타입 체인(?????)이 다르다
• 정적 메서드는 클래스로 호출하고, 프로토타입 메서드는 인스턴스로 호출한다.
• 정적 메서드는 인스턴스 프로퍼티를 참조할 수 없지만 프로토타입 메서드는 참조할 수 있다.

this에서의 차이점

• 클래스 메서드 내부의 this는 메서드를 소유한 객체가 아니라 메서드를 호출한 객체에 바인딩된다.
• 프로토타입 메서드는 인스턴스로 호출해야 하므로 프로토타입 메서드 내부의 this는 프로토타입 메서드를 호출한 인스턴스(firstStudent, secondStudent)를 가리킨다.
• 정적 메서드는 클래스로 호출해야 하므로 정적 메서드 내부의 this는 인스턴스가 아닌 클래스를 의미한다.

📌 메서드 내부에서 인스턴스 프로퍼티를 참조할 필요가 있다면 this를 써야 하기 때문에 프로토타입 메서드로 정의해야 하고, 반대 경우라면 정적 메서드로 정의하는 것이 좋다(메서드 내부에 this가 없어도 프로토타입 메서드로 정의할 수 있지만 인스턴스를 생성한 다음 호출해야 하므로 불편하다).

class StaticMethodCall {
	static staticMethod() {
    	return '정적 메서드 실행';
    }
  
  	static anotherStaticMethod() {
      	// 동일 클래스 내 다른 정적 메서드 내에서 정적 메서드를 호출하는 경우 
        // 키워드 this를 사용할 수 있다
    	return this.staticMethod() + '(다른 정적 메서드에서)'; 
    }
}

StaticMethodCall.staticMethod();        // '정적 메서드 실행'
StaticMethodCall.anotherStaticMethod(); // '정적 메서드 실행(다른 정적 메서드에서)'

class Triple {
	static triple(n) {
    	n = n || 1;
        return n * 3;
    }
}

class BiggerTriple extends Triple {
	static triple(n) {
    	return super.triple(n) * super.triple(n);
    }
}

console.log(Triple.triple());     // 3
console.log(Triple.triple(6));    // 18
BiggerTriple.triple(3);           // 81

const tp = new Triple();

console.log(BiggerTriple.triple(3));   // 81
console.log(tp.triple());              // TypeError: tp.triple is not a function
console.log(tp.constructor.triple(4)); // 12