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

👉 자료구조

데이터를 상황에 맞게 저장하고 처리하기 위한 방법

데이터를 저장, 관리하여 메모리를 효율적으로 사용하기 위해 필요하다.

👉 Linked List 

연결 리스트는 여러개의 node로 이루어져있다. 

pointer 에 의해 다음 node 를 연결한다. 

이를 통해 Linked List 는 데이터 삽입/삭제시 데이터의 구조를 재 정렬하지 않아도 된다.

 

Linked List	Array
동적 자료구조	정적 자료구조
임의 접근 불가, 순차적으로 접근해야 함	데이터의 인덱스로 임의 접근 가능
데이터 추가, 삭제에 용이	접근과 탐색에 용이
크기의 제한이 없음	수정 불가능, 배열 크기 이상의 데이터 저장 불가능

👉 Singly Linked List 

다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 가장 마지막 원소를 찾으려면 얄짤없이 리스트 끝까지 찾아가야 하기 때문에(O(n)), 마지막 원소를 가리키는 참조를 따로 가지는 형태의 변형도 있다. 보통 큐 (Queue)를 구현할 때 이런 방법을 쓴다.

 

 

Linked List 구현해보기 

연결리스트에는 추가, 검색, 삭제 기능이 있어야 한다. add, search, remove 함수로 이를 구현하였다.

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

class LinkedList {
    length = 0;
    head = null;
    
    add(value){
    	const node = new Node(value); 
        let current = this.head;
        if(!current){ //현재 head에 노드가 없으면
        	this.head = node; // 새 노드를 추가한다.
            this.length++;
            return node;
        }else{ //이미 노드가 있으면
        	while(current.next){ //마지막 노드를 찾고
            	current = current.next; 
            }
            current.next = node; //마지막 위치에 노드를 추가한다.
            this.length++;
            return node;
        }
    }
    search(position){
    	let current = this.head;
        let count = 0;
        while(count < position){ //position 위치만큼 이동한다.
        	current = current.next;
        	count++;
        }
        return current?.data;
    }
    remove(position){
    	let current = this.head;
        let before;
        let remove;
        let count = 0;
        if(position === 0){ //맨 처음 노드를 삭제하면
        	remove = this.head;
            this.head = this.head.next; //head를 두 번째 노드로 교체한다.
            this.length--;
            return remove;
        }
        //그 외의 다른 노드를 삭제하면
        while(count < position){
        	before = current;
            count++;
            current = current.next;
        }
        remove = current;
        before.next = remove.next;
        
        this.length--;
        return remove;
    }
}

 

 

참조

zerocho자료구조 Linked List

연결리스트 나무위키

 

가비지 컬렉션

JS는 객체가 생성되었을 때 자동으로 메모리를 할당한다. 그리고 더 이상 필요하지 않을 때 자동으로 해제한다.

... 후에 정리 필요