linked list

이 글을 컴퓨터 공학부 학부생이 공부하면서 작성한 글입니다. 현재 조금 더 자세한 강좌 형태의 글을 작성중이니, 부족해 보이는 부분을 댓글로 허심탄회하게 알려주시면 감사하겠습니다.

• 말 그대로 데이터와 데이터를 연결해서 리스트(List)를 구현한 것
• 데이터가 포함된 각각의 노드(node)들이 다음 데이터는 누구인지 가리킴
• 즉, 메모리 상에서 한 곳에 모여있지 않아도 리스트(List)를 구성할 수 있음

• 기본적으로 노드로 구성
• 노드는 최소 두 가지의 정보를 포함해야 함
  • 데이터
  • 다음 노드
• Linked List의 시작은 HEAD로써, 첫번째 노드를 가리킴

• Array List는 배열(Array)를 기반으로 하기 때문에 몇 번째 위치(index)에 어떤 값이 들어있는지 빠르게 알 수 있다. 이는 무작위 접근의 가능성에 기인한다.
• Array List는 Linked List에서 불가능한 무작위 접근이 가능하다. Linked List의 경우 구조적 특성 상, 순차적인 접근만이 가능하다.
• Array List는 배열을 기반으로 하기 때문에, 메모리를 연속적으로 할당해주어야 한다. 사이즈가 매우 크다면 이는 부담이 될 수 있다.
• Array List는 포인터를 사용하지 않기 때문에, 포인터 변수 만큼의 메모리 절약이 가능하다.
• Linked List의 알고리즘이 비교적 더 복잡하다.
• 데이터를 삽입하기 위해서는 List 내부에서 데이터의 이동이 필요하다. 이는 데이터 추가 / 삭제 과정에서 성능의 저하를 불러온다.