데이터 엔지니어링 데브코스 2주차 - 화요일

학습주제
[수업] 자료구조/알고리즘 : 연결리스트, 스택

주요내용

 

1. 추상적 구조

- 내부 구현은 숨기고 데이터와 연산을 제공하는 자료구조를 말한다.

- Data는 정수, 문자열 등이 될 수 있고, 연산은 삽입, 삭제, 순회, 정렬, 탐색 등의 동작하는 기능이다.

 

2. 연결리스트(Linked List)

- 데이터와 다른 데이터가 저장된 공간의 주소를 참조하고 있는 것을 '노드'라고 한다.

class Node:
	def __init__(self, item):
    	self.data = item
        self.next = None

 

- 이러한 노드의 집합을 순서대로 저장한 자료구조를 '연결리스트'라고 한다.

- 연결리스트는 가장 처음 노드와 마지막 노드의 값을 head와 tail형태로 저장하고 있다.

class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail = None

 

3. 연결리스트와 리스트 비교

 1) 저장공간(메모리 상)

  - 리스트 : 연속된 위치

  - 연결리스트 : 임의의 위치

 2) 특정 원소를 지칭할 때의 시간 복잡도

  - 리스트 : 인덱스로 접근 가능 / O(1) 

  - 연결리스트 : 선형 탐색과 유사 / O(N)

 

4. 연결리스트의 응용사례

- 리스트 내 원소를 순회하며 작업을 하다 특정 위치에 새 원소를 삽입하고 삭제하는데 용이하다.

- 반면, 배열은 삽입과 삭제를 할 때 특정 위치 이후의 원소들을 옮기는 작업이 필요하다.

- 연결리스트는 해당 위치에 다다를 경우 상수 시간에 삽입과 삭제가 가능하다.

파이썬의 배열 역시 index 메소드를 통해 새 원소를 삽입하고 삭제하는데 데이터 길이 만큼의 시간 복잡도가 소요되기 때문에 연결리스트의 삭제, 삽입과 시간 복잡도가 유사할 것이라 생각하고 관련 자료들을 찾아봤다. 아래 자료 설명에 따르면 다른 프로그래밍 언어에서는 배열과 연결리스트를 메모리 상에 저장하는 방식이 다르지만, 파이썬은 dynamic arrays 방식을 채택하고 있어서 연결리스트의 메모리 사용 방식과 유사하다고 한다.
https://realpython.com/linked-lists-python/#understanding-linked-lists 중 'Performace Comparison: Lists vs Linked List'

- 위 자료 내용은 너무나 흥미로워 차후에 자세히 정리해 볼 계획이다.

 

5. 양방향 연결리스트

- 노드의 끝 값에 도달하기 위해서는 head부터 차례대로 순차해야 하는 단방향 연결리스트의 단점을 해결하기 위한 자료구조

- 노드 객체에 이전 노드 주소와 다음 노드 주소를 함께 저장한다.

- 장점 : 단방향에 비해 순회, 삽입, 탐색이 편하다.

- 단점 : 단방향에 비해 메모리 공간을 많이 차지한다.

 

6. 스택

- 자료를 저장할 수 있는 선형 구조

- 후입선출(Last In First Out) : 가장 마지막에 들어간 값이 가장 먼저 나온다.

- push : 스택의 상단에 데이터 저장

- pop : 스택의 상단 데이터를 꺼냄

- 스택이 비어있을 때 데이터를 꺼낼 경우 stack underflow error가 발생하고, 가득 차있을 때 값을 넣을 경우 overflow error가 발생한다.

class ArrayStack:
	def __init__(self):
    	self.data = []
        
    def size(self): # 현재 스택에 들어있는 요소 개수
    	return len(self.data)
        
    def isEmpty(self): # 현재 스택이 비어 있는지 상태 확인
    	return len(self.data) == 0
        
    def push(self, item): # 스택 상단에 데이터 추가
    	self.data.append(item)
        
    def pop(self): # 스택 상단 데이터 제거 후 반환
    	return self.data.pop()
        
    def peek(self): # 스택 상단 값 확인 
    	return self.data[-1]

 

느낀점
연결리스트에 대해 잘 알고 있다고 생각했으나, 자료구조의 특정 조건들을 고려하여 코드를 작성하는게 생각보게 힘들었다. 많은 반복과 숙달이 필요할 것 같다.