연결 리스트(Linked List)

[정의]

• 데이터 요소의 선형 집합
• 이 집합에서 논리적 저장 순서는 메모리의 물리적 저장 순서와 일치하지 않는다.
• 그 대신, 각각의 원소들은 자기 자신 다음의 원소를 가리킨다. (= 링크)
• 이 자료구조는 순회하는 동안 순서에 상관없이 효율적인 삽입이나 삭제가 가능하다.
• 더 복잡한 변형은 추가적인 링크를 더해, 임의의 원소 참조로부터 효율적인 삽입과 삭제를 가능하게 한다.

 

[특징]

• 연결 리스트 내부의 노드 순서는 항상 유지된다.
• 모든 연결 리스트에는 두 개의 특수한 노드가 있다.
  첫 노드인 Head, 마지막 노드인 Tail
• Tail 노드는 다음 노드에 대한 참조 값이 없다.
• 모든 노드는 두개의 값을 가지고 있다. 데이터 값과 다음 노드에 대한 참조 값
• 모든 타입의 자바스크립트 데이터를 노드에 할당할 수 있다.

 

[배열과 연결 리스트]

배열

• 데이터를 연속된 메모리 공간에 저장한다.
• n번째 요소 접근 시 바로 접근이 가능하다.
• 배열 내 데이터 탐색의 시간 복잡도는 O(1)
  연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른위치에 쉽게 접근 할 수 있다.
  ex) 7번째 데이터를 조회하려면, 1번째 데이터에서 6번 점프하면 7번째 데이터를 조회할 수 있다.
• 배열 내 데이터 추가 및 삭제 시간 복잡도가 O(n)이다.
  배열 내 데이터를 추가하려면 추가하려고 하는 자리를 비우고 뒤에 있는 데이터를 모두 한칸씩 밀어야 하기 때문에 메모리 사용이 비효율적이다.
• 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당
• Stack 영역에 메모리 할당

 

연결 리스트

• 데이터를 연속되지 않은 메모리 공간에 저장한다.
• 데이터는 메모리 상에 고유의 노드로 존재한다.
  이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다.
• 연결 리스트 내에 특정 데이터를 조회하려면, 처음부터 순차적으로 탐색해야 한다.
  노드들이 연속된 공간에 저장되지 않고, 모두 떨어져 있기 때문이다.
• 연결 리스트 내 데이터 탐색의 시간 복잡도는 O(N)이다.
  탐색을 하기 위해서는 각 노드가 기억하고 있는 앞의 데이터와 뒤의 데이터 주소에 의지할 수 밖에 없기 때문에 노드들을 loop를 돌려서 탐색해야 한다.
• 연결 리스트 내 데이터 추가 및 삭제 시간 복잡도는 O(1)이다.
  ex) A - B - C 연결리스트에서 B와 C 사이에 Z를 추가한다면, B가 가리키는 주소 C를 Z로 변경하고 C가 가리키는 주소 B를 Z로 변경하면 되기 때문이다.
• 런타임 환경에서 메모리가 할당되는 동적 메모리 할당
• Heap 영역에 메모리 할당

연결 리스트 시각화

 

 

 

---

 

https://kimmeh1.tistory.com/473

[자료구조] Array와 Linked List의 차이는 무엇일까?

https://overcome-the-limits.tistory.com/16

[자료구조] 연결리스트 with JavaScript

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

Javascript를 이용한 Linked List 구현

https://alithedeveloper.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-with-JS-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List-1

[자료구조 with JS] 연결 리스트(Linked List) (1) 개념과 클래스

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

Javascript를 이용한 Linked List 구현