자바스크립트 자료 구조 - Lists

Data Structures and Algorithms with Javascript (Michael McMillan) 책의

Chapter 3. Lists를 정리한 내용입니다.

*코딩 독학 중인 개발자 꿈나무이기 때문에 글에 오류가 있을 수도 있습니다...!

 

 

Lists의 ADT를 만들어보자!

 

그 전에 ADT란 무엇인가? 

ADT: Abstract data type

Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of value and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation- independent view. The process of providing only the essentials and hiding the details is known as abstraction. 출처: https://www.geeksforgeeks.org/abstract-data-types/

이해한대로 정리해보자면 ADT는 자바스크립트에서 오브젝트(함수)이고,

그 안엔 여러 method들이 있어서 해당 오브젝트를 마치 하나의 data type처럼 쓸 수 있는 것.

 

ADT를 만들기 위해서는 우선 data type을 잘 정의해줘야 한다. 

정의에 따라 어떤 특성을 지니는지, 어떤 method를 포함시킬 수 있는지 결정되기 때문.

 

List는 '순서가 있는 data의 모음(ordered sequence of data)'이다.

각 data는 요소(elements)라고 부르며, 자바스크립트에서 한 list 내의 요소의 type은 서로 달라도 된다.

 

- 요소의 개수는 list의 길이를 의미하며, listSize라는 변수에 저장하자 (property)

- 요소를 list의 끝에 append 할 수 있어야 하고, (function)

- 요소를 원하는 자리에 insert 할 수도 있어야 하며, (function)

- 요소를 delete 하거나 (function)

- 모든 요소를 삭제하는 clear 기능도 있어야 한다 (function)

- 전체 요소를 프린트하는 기능(toString() 또는 .. getElement() 함수를 새로 정의)도 추가 (function)

그 밖에도

- 현재 요소의 위치 얻기 pos (property)

- 현재 요소의 위치를 다음 위치로 옮기기 next (function)

- 이전 위치로 옮기기 prev (function)

- 원하는 위치로 옮기기 moveTo (function)

등을 추가할 수 있을 것이다

 

 

ADT 구현하기 - 코드를 따라 치면서 공부.

 

- Constructor function

Constructor function으로 시작!

여기서 property는 listSize, pos, dataStore 이렇게 3개가 있다.

 

 

1) clear

우선 clear 함수를 정의.

clear 하기 위해서는 자바스크립트의 delete operator를 사용하면 된다.

 

The JavaScript delete operator removes a property from an object; if no more references to the same property are held, it is eventually released automatically. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/delete

자바스크립트의 delete operator는 object의 property를 없앤다.

해당 property의 참조가 없을 경우 자동적으로 property가 release 됨. 

 

삭제하면서 모든 property 조정 필요

dataStore를 다시 initialize 해주고, listSize와 pos도 0으로 만들어주자.

 

 

2) find

찾고자 하는 요소의 index를 반환.

해당 요소가 list 안에 없다면, -1을 반환한다.

 

 

3) remove

우선은 find 함수를 통해 제거하고자 하는 요소의 위치(index)를 얻고,

splice를 활용해 해당 index에서부터 1개의 요소를 삭제한다.

요소를 삭제했으니 listSize의 크기도 하나 줄여줘야 한다.

 

4) length, toString

toString 함수를 보면 단순히 list(dataStore)를 반환한다.

하지만 print ( ~.toString()); 을 하면

자바스크립트에서 해당 list를 string 형태로 print 해준다.

: 여기까지는 책의 설명...(2014년에 출판된)

 

Q. 자바스크립트의 모든 object에는 toString() method가 있다.

arr.toString() 하면 요소들이 comma로 연결된 string을 반환해준다.

그렇다면 ~.dataStore.toString() 해도 된다 ...

function toString () {

      return this.dataStore.toString();

}

해도 잘 작동되는 것을 확인하였다 

 - this.dataStore.toString(); 에서의 toString()은 dataStore(즉 array)의 toString 메서드.

 

 

5) insert

splice로 삭제만 할 수 있는 게 아니다!

splice(삽입할 위치, 0, 삽입할 요소);

이렇게 써주면 삽입할 위치에서부터 0개의 요소를 삭제하고 삽입할 요소를 삽입한다.

 

 

6) 그 외 position 관련된 코드들.

 

List ADT 만들기 끝.