[자바스크립트] 연결리스트, 집합 정리

1. 연결리스트

 

정의: 일련의 원소를 차례대로 저장하지만, 메모리상에서는 이웃해있지 않다. 다만 각 노드는 원소의 값과 포인터(참조정)로 구성되어 있고, 포인터는 다음 원소의 위치를 가리킨다

 

특징: 원소의 추가,삭제시 배열이 바뀌지 않지만, 특정 원소 검색시 모든 Loop를 돌아야 한다 

 

<구현>

 

head 0이 아니고 null이다 ㅠㅠ

head는 연결이 시작되는 지점을 참조한다

 

<메소드>

 

위 코드의 this.메소드에 해당되는 메소드들이다

리스트 끝에 원소를 추가하는 경우

이때 next는 다음 프로퍼티를 가리키는 포인터이다. 얘가 null이 되면 마지막 원소를 찾은 것이다

 

원소를 삭제하는 경우

이때 실제 노드는 연결이 끊어졌으므로 가비지컬렉터가 수거해 감

 

특정 위치에 원소를 추가하는 경우

특정 위치의 원소 찾기

 

<이중 연결 리스트>

 

앞뒤로 순회가 가능함

일일이 tail도 설정해줘야한다는 부분만 추가된다.

 

 

2. 집합

 

정의: Set. 중복된 원소가 없다. 

 

<구현>

 

Set의 구현

 

<Set 응용>

 

합집합, 교집합, 차집합, 부분집합으로의 사용