[자료구조]Javascript를 이용한 Linked List 구현

Linked List

Linked List는 배열과 달리 메모리상에 index에 의한 물리적 배치를 하지 않고, node를 생성 후 해당 node의 pointer에 의해 다음 node를 연결한다. 이를 통해 Linked List는 데이터 삽입/삭제시 데이터의 구조를 재정렬하지 않아도 된다.

Linked List의 이점

• 새로운 elements를 삽입, 삭제 시 용이
• restructuring이 덜 복잡함
  
  

Linked List의 단점

• array보다 많은 메모리 사용
• 특정 element를 검색시 비효율적임
  
  

Linked List 적용

• data를 연달아 추가, 삭제 시 용이
  
  

Linked List 구현

Javascript에서 연결리스트는 객체를 통해 구현할 수 있다.
아래 예시는 두개의 객체를 next로 연결하여 Linked List의 기본적인 구조를 보여준다.

const n1 = {
  data: 100
}

const n2 = {
  data: 200
}

n1.next = n2;

console.log(n1) // { data: 100, next: { data: 200 } }

연결리스트의 핵심은 node이며, node는 data를 담는 data field와 다음 노드를 알려주는 linked field로 구성된다.

 

출처: https://velog.io/@kimkevin90/Javascript%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-Linked-List-%EA%B5%AC%ED%98%84