TIL: 자료구조 | 연결 리스트 (linked list)

연결 리스트 (단순 연결 리스트)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 형태로 데이터를 저장하는 자료 구조
각 노드가 가지고 있는 포인터로 다음이나 노드와의 연결을 담당하게 된다

장점: 리스트 중간에 자료의 추가와 삭제가 O(1) 의 시간에 가능
-> 재정렬 하지 않아도 된다
단점: 특정 위치의 데이터를 검색하는데에는 O(n) 의 시간이 걸린다
-> 순차적으로 탐색하지 않으면 특정 위치 요소에 접근할 수 없다

탐색 또는 정렬을 자주하면 배열을 사용하는 편이 유리하고
추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다

연결 리스트는 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리에 연속적으로 위치하지 않는다는 점에서 배열과 다르다
배열은 인덱스로 값에 바로 접근할 수 있다는 장점이 있지만 크기가 고정되어 있고 (대부분) 배열의 처음이나 중간에 원소를 추가하거나 삭제하려면 다른 원소들까지 옮겨야 하여 비싼 연산을 수반하는 단점이 있다

연결리스트의 각 원소는 자신과 다음 원소를 가리키는 참조 정보 (포인터 or 링크) 가 포함된 노드로 구성된다

연결 리스트는 원소 추가/삭제 시 다른 원소들을 이동시키지 않아도 된다는 장점이 있다 연결리스트의 포인터가 다음 원소를 가리키게 되기 떄문이다
하지만 연결리스트에서 각 원소에 접근하기 위해서는 처음(헤드) 부터 차례대로 찾아야 한다

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

class LinkedList {
	head = new Node(data, null) 
    size = 1
}

이런 느낌..