[알고리즘/자료구조] JavaScript 연결리스트(Linked List)

연결리스트(Linked List)

• 연결리스트는 여러 개의 노드로 이루어져 있다.
• 각각의 노드는 데이터와 다음 노드의 주소를 가지고 있다. 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다.
• 새로운 데이터를 추가하거나 위치를 찾거나 제거할 수가 있다.
• 데이터의 추가/삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치 요소에 접근할 수 없어 탐색 속도가 떨어진다. 탐색/정렬을 자주 하면 배열, 추가/삭제가 많으면 연결리스트를 사용하는 것이 유리하다.

단순 연결 리스트(Singly Linked List)

이미지 출처: 나무위키

• 다음 노드에 대한 정보만을 가진 단순한 형태의 연결리스트이다.
• 가장 마지막 원소를 찾으려면 리스트 끝까지 가야해서 O(n).
• 추가는 O(1).
• head노드 유실 시 전체 자료를 잃어버리게 된다.

이중 연결 리스트(Doubly Linked List)

이미지 출처: 나무위키

• 다음 노드의 주소뿐만 아니라 이전 노드의 주소도 같이 가르키는 연결리스트 이다.
• 단순 연결 리스트에 비해 노드 삭제가 간단하다.
• 관리해야할 주소가 두 개여서 삽입이나 정렬의 경우 작업량이 더 많고 크기가 약간 더 커진다.
• head나 tail 노드 둘 중 하나만 있어도 전체 리스트를 순회할 수 있어서 끊어진 체인을 복구하는게 가능.