단일 연결 리스트 - 자료구조

---

단일 연결 리스트는 각 노드가 데이터와 다음 노드에 대한 참조(포인터)를 포함하는 데이터 구조입니다. 각 노드는 연속적으로 메모리에 저장되는 것이 아니라 불연속적인 메모리 공간에 저장됩니다. 이렇게 구현된 단일 연결 리스트는 동적인 데이터 구조를 만들기 위해 사용됩니다.

단일 연결 리스트는 하나의 헤드 노드로 시작합니다. 헤드 노드는 리스트의 첫 번째 노드를 나타내며, 이 노드에는 첫 번째 데이터와 다음 노드의 참조가 포함됩니다. 리스트의 마지막 노드는 다음 노드의 참조가 없는 노드입니다.

단일 연결 리스트는 추가, 삭제 및 검색이 가능합니다. 노드를 추가하려면 리스트의 끝에 새 노드를 추가하거나 원하는 위치에 노드를 삽입합니다. 노드를 삭제하려면 해당 노드의 이전 노드의 참조를 변경하여 노드를 건너 뛰도록 만들거나 해당 노드를 참조하는 변수를 null로 설정하여 노드를 삭제합니다. 검색을 하려면 각 노드를 탐색하여 원하는 데이터를 찾습니다.

단일 연결 리스트는 배열과 달리 인덱스가 없기 때문에 데이터를 가져오는 데에는 O(n)의 시간 복잡도가 필요합니다. 하지만 노드를 추가, 삭제하는 데에는 O(1)의 시간 복잡도가 필요하므로 동적인 데이터 구조를 만드는 데 적합합니다.

---

배열은 연결 리스트와는 달리 인덱스로 원소에 접근할 수 있는 선형 자료구조입니다. 배열에서 head와 tail은 일반적으로 다음과 같은 의미를 갖습니다.

head: 배열의 첫 번째 원소를 가리키는 인덱스입니다. 배열에서 원소를 추가할 때는 보통 head의 앞에 새로운 원소를 추가하고, 원소를 삭제할 때는 head를 한 칸 오른쪽으로 옮기는 것이 일반적입니다.

tail: 배열의 마지막 원소를 가리키는 인덱스입니다. 배열에서 원소를 추가할 때는 보통 tail의 다음 칸에 새로운 원소를 추가하고, 원소를 삭제할 때는 tail을 한 칸 왼쪽으로 옮기는 것이 일반적입니다.

즉, head와 tail은 배열에서 원소의 추가와 삭제를 할 때 사용되는 위치 지정자입니다. 이 값들을 이용하여 배열의 양 끝에서 삽입, 삭제 연산을 O(1)의 시간 복잡도로 수행할 수 있습니다.

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

class LinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    insertFirst(data){
        let newNode = new Node(data, null);

        if(this.isEmpty()){
            this.head = newNode;
            this.tail = newNode;
            this.size++;
            return;
        }

        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }

    insertLast(data){
        let newNode = new Node(data, null);

        if(this.isEmpty()){
            this.head = newNode;
            this.tail = newNode;
            this.size++
        }

        this.tail.next = newNode;
        this.tail = newNode;
        this.size++;
    }

    insertAt(idx, data){
        let newNode = new Node(data, null);

        if(this.isEmpty()){
            this.head = newNode;
            this.tail = newNode;
            this.size++;
            return
        } else if (idx == 1){
            this.insertFirst(data);
            return;
        }

        let cur = this.head;
        let count = 1;

        while(cur != null){
            if(count + 1 == idx){
                break;
            }

            cur = cur.next;
            count++;
        }

        newNode.next = cur.next;
        cur.next = newNode;
        this.size++;
    }

    removeFirst(){
        if(this.isEmpty()){
            return;
        }
        
        let cur = this.head;
        this.head = this.head.next; //null
        cur.next = null;

        this.size--;

    }

    removeLast(){
        if(this.isEmpty()){
            return;
        } else if(this.getSize() == 1){  // 하나일 때 예외처리를 생각
            this.head = null;
            this.tail = null;
            this.size--;
            return;
        }

        let cur = this.head;

        while(cur != null){
            if(cur.next == this.tail){
                break;
            }

            cur = cur.next;
        }

        cur.next =  null;
        this.tail = cur;

        this.size--;
    }

    remove(data){
        if(this.isEmpty()){
            return;
        }

        let cur = this.head;
        if(cur.data == data){  
            // this.head.data == data 즉, 첫번째 데이터가 동일하다면
            this.head = cur.next;
        } else {
            while(cur != null){
                // 이대로 값 검색이 안되고 끝까지 왔다면
                if(cur.next == null){
                    return;
                }
                if(cur.next.data == data){
                    break;
                } 

                cur = cur.next;
            }

            cur.next = cur.next.next;
        }

        this.size--;
    }

    search(data){
        let idx = 1;
        let cur = this.head; 

        while (cur != null){
            if(cur.data == data){
                console.log(`${idx}번째에 '${data}'가 있습니다.`);
                return;
            }

            cur = cur.next;
            idx++;
        }
        console.log(`'${data}'가 존재하지 않습니다.`);
    }

    print() {
        let cur = this.head;

        console.log((`=== 크기 : ${this.getSize()} ===`));
        while(cur != null){
            console.log(cur.data);
            cur = cur.next;
        }
    }

    getSize() {
        return this.size;
    }

    isEmpty(){
        return !this.size;
    }
}

const linkedList = new LinkedList();

linkedList.insertFirst("화");
linkedList.print();
linkedList.insertFirst("월");
linkedList.print();
linkedList.insertLast("금");
linkedList.print();
linkedList.insertAt(3, "목");
linkedList.print();
linkedList.insertAt(3, "수");
linkedList.print();

linkedList.search("월")
linkedList.search("화")
linkedList.search("수")
linkedList.search("목")
linkedList.search("금")
linkedList.search("토")
linkedList.search("일")

// linkedList.removeFirst();
// linkedList.print();
// linkedList.removeFirst();
// linkedList.print();


// linkedList.removeLast();
// linkedList.print()
// linkedList.removeLast();
// linkedList.print()
// linkedList.removeLast();
// linkedList.print()
// linkedList.removeLast();
// linkedList.print()
// linkedList.removeLast();
// linkedList.print()
// linkedList.removeLast();
// linkedList.print()


linkedList.remove("일");
linkedList.print();
linkedList.remove("화");
linkedList.print();
linkedList.remove("목");
linkedList.print();
linkedList.remove("금");
linkedList.print();
linkedList.remove("수");
linkedList.print();
linkedList.remove("월");
linkedList.print();
linkedList.remove("금");
linkedList.print();
linkedList.remove("토");
linkedList.print();

각 메소드들이 어떤 기능을 하는지 보면서 이해해보겠습니다.

• Node 클래스: 데이터와 다음 노드의 주소를 가지는 노드 객체를 생성하는 클래스
• LinkedList 클래스: 연결 리스트 객체를 생성하는 클래스

LinkedList 클래스의 메소드들:

• insertFirst(data): 연결 리스트의 맨 앞에 데이터를 추가하는 메소드
• insertLast(data): 연결 리스트의 맨 뒤에 데이터를 추가하는 메소드
• insertAt(idx, data): 연결 리스트의 idx 위치에 데이터를 추가하는 메소드
• removeFirst(): 연결 리스트의 맨 앞 데이터를 삭제하는 메소드
• removeLast(): 연결 리스트의 맨 뒤 데이터를 삭제하는 메소드
• remove(data): 연결 리스트에서 데이터를 검색하여 삭제하는 메소드
• search(data): 연결 리스트에서 데이터를 검색하는 메소드
• print(): 연결 리스트의 내용을 출력하는 메소드
• getSize(): 연결 리스트의 크기를 반환하는 메소드
• isEmpty(): 연결 리스트가 비어있는지 확인하는 메소드