04.11 데이터 엔지니어링 2일차 - 자료구조/알고리즘 (2)

추상적 자료구조 (Abstract Data Structures)

• Data (정수, 문자열, 레코드, ...)
• A set of operatations (삽입, 삭제, 순회 ...)

연산 정의

1. 특정 원소 참조 (k번째)
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

배열과 비교한 연결 리스트

	배열	연결 리스트
저장 공간	연속한 위치	임이의 위치
특정 원소 지칭	매우 간편	선형탐색과 유사

                                             O(1)                                     O(n)

 

코드 구현 주의사항

1. 삽입하려는 위치가 리스트 맨 앞일 때 

-> prev 없음

-> Head 조정 필요

단, 빈 리스트에 삽입할 때? -> 이 두 조건에 의해 처리됨

2. 삽입하려는 위치가 리스트 맨 끝일 때

-> Tail 조정 필요

 

연결 리스트의 핵심 연산

• 원소의 삽입 (insertion)
• 원소의 삭제 (deletion)
• 두 리스트 합치기 (concaenation)

연결 리스트를 다루는 프로그래밍을 연습해보면서 생각해야 할 점

1. 이것이 무엇을 위함이냐? 즉, 연결 리스트라는 자료 구조를 착안함으로써 어떤 목적을 이루고자 했는지, 연결 리스트가 가지는 장점이 어떤 곳에서 발휘되는지, 알고리즘의 복잡도 측면에서 생각하기
2. 링크를 조정하는 등의 코딩은 앞으로 나타나게 될 트리(tree)라든지, 이 강의 시리즈에서 다루지는 않지만 그래프 등을 프로그래밍 할 때를 대비한 연습이 된다는 점을 떠올리기

 

더미 노드(dummy node) : 데이터 원소를 담고 있지 않은 노드 

 

스택 (Stacks) 이란?

마치 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조

• 푸시(push)연산 : 스택에 데이터 원소를 추가
• 팝(pop)연산 : 마지막에 추가되었던 원소를 참조하고 삭제하는 (꺼내는) 동작

 

후위 표기법(Postfix Notation)이란?

연산자를 두 피연산자의 뒤에 쓰는 방식 

ex) 중위 표기법: A + B -> 후위 표기법:  A B +

1. 수식을 왼쪽부터 시작해서 오른쪽으로 차례대로 읽어들이면서
2. 피연산자가 나타나면, 스택에 넣어 둔다.
3. 연산자가 나타나면, 스택에 들어 있는 피연산자를 두 개 꺼내어 연산을 적용하고, 그 결과를 다시 스택에 넣어 둔다.

를 반복하면 마지막에 모든 연산이 적용된 결과가 스택에 유일하게 남아 있게 된다.