너무너무 늦은 링크드리스트 정리....

• 여기서는 single linked list만 정리

linked list 연결리스트

출처: https://www.alphacodingskills.com/

여러가지 자료를 일정한 길이의 리스트에 분류한 자료구조.
데이터와 다음 노드의 주소값을 가진 노드를 연결시킨 자료구조
순서 보장 x

ex) 책꽂이에 나의 물건을 정리하는 것
    책꽃이 = 링크드리스트
    나의 물건 = 링크드리스트에 넣을 자료

• 노드란?
  링크드리스트의 구성요소로 데이터를 갖고 있는 데이터의 묶음

일정한 길이의 리스트라고 하면 배열과 착각할 수 있지만
길이가 고정된 배열과 달리 링크드리스트는 필요에 따라 리스트의 길이를 변경할 수 있다.

가장 앞에 있는 노드는 head, 가장 뒤에 있는 노드는 tail이라고 한다.

시간 복잡도

삽입: O(1)
삭제: O(1)
탐색: O(n)

삽입, 삭제는 자료 하나를 그냥 넣고 양옆의 노드에 next 자료만 변경하면 되기 때문데 평균적으로 O(1)이다.

탐색의 경우 배열처럼 head부터 head의 next를 따라 tail까지 이동하면서 탐색하기 때문에 시간 복잡도는 O(n)이 된다.

자료 출처 : https://burger-and-fries.tistory.com/13

링크드리스트 구현

링크드리스트의 구성 요소인 node 구현

const createNode = function (value) {
	const node = {};
    
    node.value = value;
    node.next = null;
    
    return node;
}

링크드리스트 list 구현

const createLinkedList = function () {
	const list = {};
    //head, tail 형식 만들어주기
    list.head = null;
    list.tail = null;
	
    return list;
}

링크드리스트의 tail에 노드 삽입

list.addToTail = function (value) {
	const newNode = createNode(value);
    
	if (!this.head) {
    	this.head = newNode;
        this.tail = newNode;
        return;
    }
    
    this.tail.next = newNode;
    this.tail = newNode;
}

링크드리스트의 head 삭제(head 삭제 후 삭제한 데이터 반환)

list.removeHead = function () {
	if (!this.head) {
    	return null;// head가 없으면 removehead를 할 수 없고 초기값인 null을 반환
    }
	const headValue = this.head.value;
    this.head = this.head.next;
    
    return headValue;
}

특정 요소 포함 여부 판별

list.contains = function (target) {
	const currentNode = this.head;
    
    while (currentNode) {
    	if (currentNode.value === target) {
        	return true;
        }
        
        currentNode = currentNode.next;
    }
    
    return false;
}