Data Structures & Algorithms with Javascript : Lists

[이전글] 2024.07.17 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Arrays

Data Structures & Algorithms with Javascript : Arrays

💭 저번 글에서는 가장 기본적인 자료구조인 Array를 자바스크립트 내장 함수 예제와 함께 살펴봤다.
🧾 List 자료 구조의 경우 검색이나 데이터의 저장 순서가 중요하지 않은 경우 사용할 때 바람직하다.
👩🏻‍💻 이번에는 추상 데이터 타입(ADT: abstract data type) 리스트의 정의와 구현 방식에 대해 알아보자.

ADT 리스트

List란?

리스트는 정렬된 데이터의 연속이다. 리스트에 저장된 데이터 아이템은 'element(엘리먼트)'라고 한다.

자바스크립트에서 엘리멘트 리스트는 어떠한 데이터 타입을 저장할 수 있다. 

List의 속성

리스트는 위치를 나타내는 속성을 지닌다. 

리스트의 front와 end 사이에서 next() 연산을 통해 다음 엘리먼트로 옮겨갈 수 있고, prev() 연산을 통해 이전 엘리먼트로 접근 가능하다.

moveTo(n) 연산을 통해서 리스트의 n번째 위치로 이동할 수 있다.

currPos로 현재 위치를 나타낼 수 있다.

 

ADT List 구현

리스트의 속성을 통해 다음과 같은 속성과 함수를 정리할 수 있다.

이름	분류	설명
listSize	속성	리스트 내의 엘리먼트의 개수
pos	속성	리스트 상의 현재 위치
length	속성	엘리먼트의 개수 리턴
clear	함수	리스트의 모든 요소 제거
toString	함수	리스트를 string으로 리턴
getElement	함수	현재 위치의 엘리먼트 리턴
insert	함수	새로운 엘리먼트를 존재하는 엘리먼트 뒤에 추가
append	함수	새로운 엘리먼트를 리스트 맨 끝에 추가
remove	함수	엘리먼트 삭제
front	함수	현재 위치를 리스트 맨 앞 엘리먼트로 설정
end	함수	현재 위치를 리스트 맨 끝 엘리먼트로 설정
prev	함수	현재 위치를 다음 엘리먼트 위치로 이동
next	함수	현재 위치를 이전 엘리먼트 위치로 이동
currPos	함수	리스트 상 현재 위치 리턴
moveTo	함수	현재 위치를 특정 위치로 이동

 

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

class List {
    constructor(){
        this.listSize = 0;
        this.pos = 0;
        this.dataStore = [];
    }
	// 엘리먼트의 위치 혹은 존재하지 않는다면 -1을 반환한다.
    find(element){
        for(let i=0; i< this.dataStore.length; i++){
            if(this.dataStore[i] == element){
                return i;
            }
        }
        return -1;
    }
    
    // 새로운 엘리먼트 추가
    append(element){
        this.dataStore[this.listSize++] = element;
    }
    
    // 리스트에 존재하는 엘리먼트 삭제
    remove(element){
        let foundAt = this.find(element);
        if(foundAt > -1){
            this.dataStore.splice(foundAt,1);
            --this.listSize;
            return true;
        } return false;
    }
    
    // 리스트의 길이 리턴
    length(){
        return this.listSize;
    }
    
    // 리스트 엘리먼트를 콤마로 구분한 하나의 string 형태로 리턴
    toString(){
        return this.dataStore.join(' ,');
    }
    
    // 엘리먼트를 특정 위치에 삽입 
    insert(element, after){
        let insertPos = this.find(after);
        if(insertPos > -1){
            this.dataStore.splice(insertPos+1,0,element);
            ++this.listSize;
            return true;
        } return false;
    }
    
    // 리스트 비우기
    clear(){
        delete this.dataStore;
        this.dataStore = [];
        this.listSize = this.pos = 0;
    }
    
    // 리스트에 엘리먼트 존재 여부 확인
    contains(element){
        const elementIndex = this.find(element);
 		return elementIndex > -1;
    }

	// 리스트 맨 앞으로 위치 이동
    front(){
        this.pos = 0;
    }
    // 리스트 맨 뒤로 위치 이동
    end(){
        this.pos = this.listSize-1;
    }
    
    // 이전 엘리먼트 위치로 이동, 맨 첫 엘리먼트라면 제자리
    prev(){
        if(this.pos > 0){
            --this.pos;
			return true;	// 이전 요소가 있을 경우 true
        }
		return false;
    }
    
    // 다음 엘리먼트 위치로 이동, 맨 끝 엘리먼트라면 제자리
    next(){
        if(this.pos < this.listSize-1){
            ++this.pos;
			return true; // 다음 요소가 있을 겨우 true
        }
		return false;
    }
    
    // 현재 위치 리턴
    currPos(){
        return this.pos;
    }
    
    // 특정 위치로 이동
    moveTo(position){
        this.pos = position;
    }
    
    // 현재 위치의 엘리먼트 리턴
    getCurrentElement(){
       return this.dataStore[this.pos];
    }
 
}
const print = (item)=> console.log(item);

const alphabets = new List();
alphabets.append('a');
alphabets.append('A');
alphabets.append('b');

 

리스트를 사용해 보면 다음과 같이 동작한다.

const print = (item)=> console.log(item);

const alphabets = new List();
alphabets.append('a');
alphabets.append('A');
alphabets.append('b');
print(alphabets.toString()); // a ,A ,b
print(alphabets.getCurrentElement()); // a
alphabets.moveTo(2);
print(alphabets.currPos()); // 2
alphabets.prev();
print(alphabets.currPos()); // 1
alphabets.insert('added','a'); 
print(alphabets.toString()); // a ,added ,A ,b
alphabets.remove('added');
print(alphabets.toString()); // a ,A ,b
print(alphabets.currPos()); // 1
alphabets.next();
print(alphabets.currPos()); // 2
alphabets.clear();
print(alphabets.toString()); // ''

 

리스트를 통해 iterator의 특징을 엿볼 수 있다.

Iterator

iterator는 list 클래스의 내부 저장 메커니즘을 참조하지 않고 front(), end(), prev(), next()와 currPos()로 리스트를 순회할 수 있도록 한다. iterator를 사용하면  리스트 엘리먼트 접근 시 데이터 저장소의 구조에 대한 걱정을 안 해도 되고, iterator를 업데이트 하지 않고도 list를 업데이트할 수 있다.

 

리스트 순회

// 리스트 순회
alphabets.front(); // 리스트 첫 엘리먼트에서 시작
while (alphabets.currPos() < alphabets.length()) {
    print(alphabets.getCurrentElement());
    if (!alphabets.next()) {
        break;
    }
}

// 리스트 역으로 순회
alphabets.end(); 
while (alphabets.currPos() >= 0) {
    print(alphabets.getCurrentElement());
    if (!alphabets.prev()) {
        break;
    }
}

 

👩🏻‍🔧 오늘은 리스트 자료 구조에 대해 살펴봤다. 
🍀 책에 오류? 가 많았다. 안 돌아가는 코드, 무한루프에 빠지는 순회 코드.. 오히려 개념 틀만 가져가고 직접 구현하니까 럭키비키잖아!

 

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9