[자료구조] Linked List

예전 포스팅 옮기는 중

---

Linked List ( 연결리스트 )

github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/linked-list/README.ko-KR.md

trekhleb/javascript-algorithms

선형 데이터 구조이다
논리적 저장 순서는 메모리의 물리적 저장 순서와 일치하지않는다
각각의 요소들은 자기 자신 다음의 요소를 가리킨다.
순서를 표현하는 노드들의 집합으로 이루어져 있다.
각각의 노드들은 데이터와 다음 순서의 노드를 가리키는 레퍼런스(=링크=주소)로 이루어져 있다.

효율적인 삽입과 삭제가 가능하다.

그러나 접근 시간이 선형이고, 병렬 처리를 할 수없다. 빠른 접근은 불가능 하다.

배열이 연결 리스트보다 더 나은 캐시 지역성(cache locality)을 가지고 있다.

배열은 물리적으로 붙어있다. 배열은 길이를 변경( 중간에 삽입,삭제 등)을 할 때, 연결 리스트보다 복잡하다.

연결 리스트는 그냥 삽입할 값을 가리키게만 하면 되서 더 간단하다. 다만, 배열보다 느림

첫번째 노드는 head라고 부른다. 마지막 노드는 null을 가리킨다.

 

지역성 ( locality )

blog.skby.net/%EC%A7%80%EC%97%AD%EC%84%B1-locality/

지역성 (Locality) > 도리의 디지털라이프

복잡도

시간복잡도

접근	탐색	삽입	삭제
O(n)	O(n)	O(1)	O(1)

공간복잡도

O(n)

 

자바스크립트로 구현하기

// Node 클래스
class Node{
	constructor(data,next=null){ // 마지막 노드는 null을 가리켜야하기때문에
    	this.data = data;
        this.next = next; // 다음 노드를 가리킨다.
    }
}

// Linked List
class LinkedList{
	constructor(){
    	this.head =null; // 첫번 째, 노드
        this.size = 0; // 리스트의 크기
    }
    // 맨 앞에 노드 추가하기
    insertFirst(data){
    // this.head를 next로 지정한 이유는 
    // 이미 head노드가 존재 할 경우, head노드를 밀어내고
    // 자신이 head노드가 되기때문에 현재의 head 노드를 가리켜야한다.
    // head가 없으면 null 값이 들어감, next가 null이면 마지막 노드라는 뜻
    	this.head = new Node(data, this.head);
        this.size++;
    }
    
    // 맨 뒤에 노드 추가하기
    insertLast(data){
    	let node = new Node(data); // 맨 마지막이니까 next는 디폴트로 null
        let current;
        
        // 만약 List가 비어있다면
        if(!this.head){
        	// head에 node를 넣는다.
        	this.head = node;
        }else{
        	// List의 맨 마지막을 찾는다.
        	current = this.head; // head부터 current로 두고 맨 뒤를 찾는다.
            while(current.next){ // next가 null이면 멈춘다. = 맨 뒤 노드라는 의미
            	current = current.next; 
            }
            // 현재 노드의 next가 null인 노드를 찾아서 while문 탈출
            // 현재 노드의 next에 추가할 node를 붙인다.
            current.next = node;
        }
        this.size++;
    }
    // 원하는 index에 노드 추가하기
    insertAt(data,index){
        // index 범위가 잘못 되어있을 경우
        if( index < 0 || index > this.size) return;
        
        // index가 0 (첫번째) 일 경우
        if( index == 0 ){
        	this.insertFirst(data);
            return;
        }
        
        // 추가할 노드 생성
        const node = new Node(data);
        // 현재와 이전 노드를 담을 변수 생성
        let current, previous;
        
        // index에 있는 노드 위치를 파악하기
        current = this.head;
        let count = 0; // index위치를 세기위한 변수
        while(count < index){
        	previous = current; // 한 번씩 루프를 돌 때마다, 현재 노드는 이전 노드가 됨
            count++; // 한 번 돌때마다 추가
            current = current.next // 현재 노드는 현재노드가 가리키는 다음 노드(next)가 됨
        }
        // 앞(next), 뒤(previous)에 있을 노드 정보를 가지고 while문 탈출
        node.next = current;
        previous.next = node;
        
        this.size++;
    }
    
    // Get at index, 인덱스로 데이터얻기
    getAt(index){
    	let current = this.head;
        let count = 0;
        // count와 index가 같아질 때 까지 loop
        while(current){
        	if(count == index){
            	console.log(current.data);
            }
            count++;
            current = current.next;
        }
        return null;
    }
    
    // remove at index, 인덱스 노드 지우기
    removeAt(index){
    	// 올바른 index 범위 확인
        if( index < 0 && index > this.size) return;
        
        let current = this.head;
        let previous;
        let count = 0;
        
        // index가 0일 경우 , remove First
        if(index == 0){
        	// head를 다음 노드로 바꿔버림
        	this.head = current.next;
        }else{
        	while(count < index){
            	// 삭제할 index 찾기
            	count++;
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.size--;
    }
    
    // List 다 지우기
    clearList(){
    	// head를 없애버리면 된다.
        // head가 사라져서 더이상 리스트가 연결되지않는다
    	this.head = null;
        this.size = 0;
    }
    
    // Print List
    printListData(){
    	let current = this.head;
        while(current){
        	console.log(current.data);
            current = current.next;
        }
    }
}