js 연결리스트(Linked List)

Linked List의 맨 앞을 head 라하고 맨 마지막은 tail이라고 한다. 

이 노드들은 다음에 올 노드의 정보를 가지고 있다.

예) 식탁에서 "안방으로 가시오"라는 쪽지를 붙여두었다. 안방에서는 "안방화장실로 가시오"라고 붙였다.

 쪽지에 써있는 다음 장소의 정보를 읽어야 하는 구조가 연결리스트이다.

Linked list는 배열과 비교했을 때 특정 데이터를 검색하는데 시간이 오래걸린다. 배열은 index로 공간의 주소가 인덱스라는 것으로 정해져있기 때문이다. 어떤 값의 주소만 알고있으면 값을 찾는 것은 쉽다. O(1)이다. Linked List는 링크로 연결되어있고 각 요소들은 다음의 주소만을 가지고 있어 어떤 값을 찾기 위해서는 링크를 타고가야한다. O(n).

그대신 배열은 중간에 어떤 요소를 삽일 할때 어떤 요소를 넣으려면 다음 요소드르이 위치를 다 밀어야한다. O(n)

Linked List는 중간에 삽입하더라도 옆공간에 넣을 필요없이 이전 요소가 새로운 요소를 가리키기만 하면 된다. O(1)

 

 

 

 

 

 

 

Big O: 자료를 삽입하려면 자료를 추가할 장소로 가서 기존의 링크를 끊은 다음 

추가할 위치의 이 전 요소의 꼬리와 삽입할 자료의 꼬리를 연결한다.

추가할 요소의 꼬리와 다음 요소의 꼬리를 연결한다. 

앞 요소와 다음 요소와 연결시켜주는 연산만 수행되므로 시간 복잡도는 O(1)이다. 

삭제하려면 삭제하고자 하는 요소의 이 전 요소의 꼬리를 다음 요소와 연결 시켜주면된다.

삭제하고자 하는 요소의; 이 전 요소와 다음 요소를 연결시켜주는 연산이 수행되므로 시간 복잡도는 O(1)이다.

자료를 검색하고 싶다면 맨 앞의 head에서부터 시작한다.

연결 리스트의 각 노드들은 다음 요소들의 정보를 가지고 있기 때문에 맨 앞의 리스트에서부터 다음 노드들을 순차적을 검색해야 한다. 시간 복잡도는 O(n)이다.