[Basic of Basic] 알고리즘 기본 정리 - 단방향 리스트와 양방향 리스트

출처: Yes24

본 포스팅은 '그림으로 배우는 알고리즘 Basic' - 스기우라 켄 저, 영진닷컴 출판 - 을 공부하며 정리한 포스팅입니다

 

1. 자료구조 - 배열. 리스트

단방향 리스트와 양방향 리스트를 배우기 앞서 배열과 리스트에 대해 간단히 짚고 넘어가 보도록 하자.

앞선 포스팅에서 말했듯이 배열이란 '데이터를 빈틈없이 나열한 자료구조'이다. 반면 리스트는 데이터를 순서대로 나열한 자료구조이다. 얼핏 보면 두 자료구조가 크게 다르지 않아 보일 수 있지만 두 자료구조는 다른 특징을 가지고 있다.

 

• 배열과 리스트
  • 배열
    • 1차원 배열의 경우 요소를 일직선 상에 빈틈 없이 나열하여 리스트를 정렬한다
    • 조회가 빠르다
    • 삽입. 삭제 시 오래 걸린다
  • 리스트
    • '방향성이 있는 끈'으로 각각의 요소들을 연결시켜 데이터를 정렬한다 
    • 조회가 느리다(조회하는 요소가 뒤에 있을수록 검색 시간 비용이 커지고 속도도 늦어진다)
    • 삽입. 삭제 시 빠르다(포인터 조작으로 빠르게 가능하다)

파이썬의 경우 배열과 리스트가 클래스로 구현되어 있다. (출처: https://i.stack.imgur.com)

대량의 데이터를 효율적으로 다루기 위한 자료구조의 대표적인 자료구조인 '배열과 리스트'에 대해 적어도 이 정도의 지식은 가져갔으면 한다.

 

 

• 자료구조
  • 배열
  • 리스트
    • 단방향 리스트
    • 양방향 리스트

 

2. 단방향 리스트

• 한쪽 방향에서 데이터를 찾아가는 단방향 리스트
• 리스트 안에서, '앞쪽에서 뒷쪽으로 가리키는 방향성을 가진 끈'으로 순서가 있는 데이터를 연결하는 방식을 단방향리스트라고 한다.
• 단방향 리스트의 두 가지 요소
  • 데이터
  • 다음 요소를 가리키는 포인터

(출처: https://media.geeksforgeeks.org)

위의 그림과 같이 맨 앞의 데이터를 가리키는 'Head' 포인터가 있으며 각각의 값은 '데이터'와 다음 요소를 가리키는 '포인터'(Next Pointer)로 이루어져 있다.

 

3. 양방향 리스트

• 리스트 안에서 앞에서 뒤를 가리키는 끈과 뒤에서 앞을 가리키는 끈 2개를 사용하여 순서가 있는 데이터를 연결하는 방법을 '양방향 리스트'라고 부르다
• 양방향 리스트의 세 가지 요소
  • 데이터
  • 다음 요소를 가리키는 포인터
  • 이전 요소를 가리키는 포인터

Doubly Linked List (출처: https://media.geeksforgeeks.org)