자료구조

• 자료구조란 ?

  • 데이터들이 어떤 형태로 이루어져 있는가 ? 어떻게 구성되어 있는가 ?
  • 자료구조에 따라 데이터가 저장되거나 사용하는 방법이 달라진다.

• 자료구조를 배워야 하는 이유

  • 상황에 맞게 효율적으로 데이터를 관리하고 사용하기 위해서
    • 배열은 데이터 탐색은 빠르지만 데이터의 추가가 어렵거나 느리다. 반면에 연결리스트는 데이터 추가는 빠르지만, 탐색은 앞에서부터 순차적으로 하므로 느리다.
  • 문제 해결을 위해서
  • 언어나 사람에 따라서 구현되는 코드는 다르지만, 추상적인 개념에 대해서만 알고 있어도 사용 가능하다.

추상 자료형(Abstrac Data Type, ADT)

• 추상화
  • 핵심적인 개념 또는 기능을 간추려 내는것
  • 실존하지 않은 자료구조의 로직을 정의해 놓은 것
    • 마름모, 정사각형, 사다리꼴 공통점 : 도형, 네개의 각, 네개의 변 이 공통요소들을 일일이 언급하지 않고 ‘사각형’ 이라고 부르는것이 추상화의 예
• 자료 구조에서의 추상화
  • 세부적인 구현으로부터 분리해 개념을 일반화 시킨것
    • 무엇인지는 정의하지만, 어떤 언어를 사용해서 어떻게 구현할지는 정의하지 않는다.
    • 오늘 배우는 연결리스트, 큐, 스택 이게 모두 추상적 자료구조이다.
      • 자료구조의 방법이 코드로 정의된 것이 아니라, 그 구조의 행동 양식만 정의된 것을 의미
      • 규칙을 이해하면 직접 코드로 구현할 수 있음

자료 구조 - 위키백과, 우리 모두의 백과사전

연결리스트

• 구성 : 데이터 + 포인터

  • 포인터 : 다음 노드를 가리킬 위치정보

• 장점 :

  • 유동적으로 조절이 가능해서 리소스를 아낄 수 있다.

    → 데이터의 추가, 제거가 쉽다

  • 시간복잡도가 상수 O(1)

  IT위키

• 단점

  • 단순 배열보다 용량이 크다
  • 탐색이 오래걸린다. (인덱스를 사용할 수 없다.)

• 연결리스트의 시간복잡도

  • 검색 : 최선O(1) / 최악O(n)
  • 추가 및 제거 : 추가O(1)
  • 특정 값이 있는 위치에 추가 및 제거 : O(n)

배열 vs 연결리스트

• 인덱스 접근
  • 배열은 가능, 연결리스트는 불가능
• 길이
  • 배열은 길이가 정해져 있지만, 연결리스트는 가변
• 배열은 값들이 메모리를 연속적으로 차지하지만, 연결리스트는 메모리상에서 붙어있지 않아도 된다.

# 연결리스트 간단하게 구현해보기
class Node :
	def __init__(self, value, next = None):
		self.value = value
		self.next = next