[자료구조] 연결 리스트 - (1) Single Linked List

연결 리스트

배열(일종의 리스트)

• 장점: 구현하기가 쉽고 사용하기 편하다.
• 배열의 원소에 접근하려면 대괄호에 인덱스만 넣어주면 된다.
• 단점
• 크기가 고정되어 있다
• 배열의 처음이나 중간에서 원소를 추가/삭제 하려면 다른 원소까지 옮겨야 하므로 번거롭다

 

연결리스트(Linked List)

• 연결리스트는 일련의 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치하지 않는다
• 각 원소는 원소 자신과 다음 원소를 가리키는 참조 정보(포인터,링크 라고도함)가 포함된 노드로 구성된다
• 장점: 원소 추가 삭제 시 다른 원소들을 이동하지 않아도 된다(포인터 덕분)
• 단점: 배열은 특정 원소에 인덱스로 바로 접근할 수 있는 반면 연결 리스트에서는 원소를 찾을 때까지 처음(헤드,head)부터 루프를 반복해야함
• 연결리스트의 예시
• 서로 손잡고 원을 그리며 춤추는 것에 비유
• 사람들 각자가 원소, 자신의 손이 옆 사람과 연결되는 포인터
• 새로운 사람이 들어오려면 들어갈 위치에서 연결을 잠시 끊은 뒤 다시 옆사람과 손을 잡으면 된다

 

배열과 연결리스트의 시간 복잡도

연결리스트의 종류

 

연결리스트(Single Linked List) - 자바스크립트 코드로 구현

//연결 리스트 만들기

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

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

    //1. append(element) : 가장 뒤에서 원소를 삽입
    append(element){
        let node = new Node(element);
        let current = this.head;

        if(this.head === null){
            this.head = node;
        }else{
            while(current.next){
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }

    //2. insert(position, element) : 원하는 위치에 원소를 삽입
    insert(position,element){
        if(position >=0 && position <= this.length){
            let node = new Node(element);
            let current = this.head;
            let previous;
            let index = 0;

            if(position === 0){
                node.next = current;
                this.head = node;
            }else{
                while(index < position){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = node;
                node.next = current;

            }
            this.length++;
            return true;
        }else{
            return false;
        }
    }

    //3. removeAt(position) : 원하는 위치의 원소를 삭제
    removeAt(position){
        if(position > -1 && position < this.length){
            let current = this.head;
            let previous;
            let index = 0;

            if(position === 0){
                this.head = current.next;
            }else{
                while(index < position){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }
            this.length--;
            return current.element;
        }else{
            return null;
        }
    }

    //4. indexOf(element) : element의 index를 반환
    indexOf(element){
        let current = this.head;
        let index = 0;

        while(current!==null){
            if(element === current.element){
                return index;
            }

            index++;
            current = current.next;
        }
        return -1;
    }

    //5. remove(element): 해당 element를 삭제
    remove(element){
        let index = this.indexOf(element);

        return this.removeAt(index);
    }

    //6. toString()
    toString(){
        let current = this.head;
        let string = '';

        while(current!==null){
            string += current.element+",";
            current = current.next;
        }
        return string;
    }

    //7. size()
    size(){
        return this.length;
    }

    //8. isEmpty()
    isEmpty(){
        return this.length == 0;
    }
    
    //9. getHead() - head를 받아오는 메소드
    getHead(){
    	return this.head;
    }
    
}

let linkedlist = new LinkedList();
linkedlist.append("짱구");
linkedlist.append("철수");
linkedlist.append("맹구");
console.log(linkedlist.toString()); //짱구,철수,맹구,

linkedlist.insert(2, "훈이");
linkedlist.insert(2, "유리");
console.log(linkedlist.toString()); //짱구,철수,유리,훈이,맹구,

linkedlist.removeAt(1);
console.log(linkedlist.toString()); //짱구,유리,훈이,맹구,

linkedlist.append("원장선생님");
console.log(linkedlist.toString()); //짱구,유리,훈이,맹구,원장선생님,

console.log(linkedlist.indexOf("짱구")); //0

linkedlist.remove("원장선생님");
console.log(linkedlist.toString()); //짱구,유리,훈이,맹구,

console.log(linkedlist.size()); //4
console.log(linkedlist.isEmpty()); // false