자료구조 & 알고리즘 - 2

연결리스트(Linked Lists)

- 데이터의 논리적 순서를 유지하면서, 물리적인 저장 위치는 다를 수 있는 데이터 구조

- 데이터의 추가, 삭제가 빈번한 상황에서 유용하게 사용된다.

- 연결 리스트는 노드(Node)들의 연결로 구성되며, 각 노드는 데이터와 포인터(Pointer)로 구성된다.

* 포인터는 다음 노드를 가리키는 포인터(next 포인터)와 이전 노드를 가리키는 포인터(prev 포인터)가 있다.

* 데이터는 노드에 저장하는 값이다.

- 이러한 구조 때문에 연결 리스트는 단방향 연결 리스트(Singly Linked List)와 양방향 연결 리스트(Doubly Linked List)로 구분된다.

 

단방향 연결 리스트(Singly Linked List)

- 각 노드는 다음 노드를 가리키는 포인터(next 포인터)만 가지고 있다.
- 첫 번째 노드를 헤드(Head)라고 하며, 마지막 노드는 꼬리(Tail)라고 한다.

 

1) 연결리스트의 단점

- 선형 배열에 비해서 데이터 구조 표현에 소요되는 저장 공간 (메모리) 소요가 크다.
- 연결 리스트는 배열(Array)과 달리 인덱스가 없기 때문에, 원하는 노드에 직접 접근할 수 없다.

- 연결 리스트에서는 원하는 노드를 찾기 위해서 첫 번째 노드부터 순차적으로 탐색해야 한다.

- 이러한 특성 때문에, 연결 리스트에서의 탐색은 선형 시간(Linear Time)이 소요된다.

* 선형 시간: 입력 크기에 비례하는 시간 복잡도를 가지는 알고리즘으로 입력 데이터의 크기에 따라 실행 시간이 선형적으로 증가

 

2) 연결리스트의 장점

- 삽입과 삭제가 유연하다.

 

3) 연결리스트와 배열간의 차이점

구분	배열	연결 리스트
저장 공간	연속한 위치	임의의 위치
특정 원소 지칭	인덱스로 빠르게 접근	선형탐색과 유사(인덱스 접근X)
표기	특정 인덱스를 이용하여 원소를 참조 => O(1)의 시간 복잡도	특정 노드를 찾기 위해서는 처음부터 순차적으로 탐색 => O(n)의 시간 복잡도

 

4) 연결리스트 연산 정의

- 삽입(Insert) : 연결 리스트에 새로운 노드를 추가

* 맨 앞에 삽입하는 경우: O(1)

* 맨 뒤에 삽입하는 경우: O(1)

* 중간에 삽입하는 경우: O(n)

- 삭제(Delete) : 연결 리스트에서 특정 노드를 삭제

* 맨 앞에 삽입하는 경우: O(1)

* 맨 뒤에 삽입하는 경우: O(n)

* 중간에 삽입하는 경우: O(n)

- 탐색(Search) : 연결 리스트에서 특정 데이터를 찾기
- 출력(Print) : 연결 리스트에 저장된 모든 데이터를 출력

- 길이(Length): 연결 리스트의 길이를 반환하는 것 O(1)
- 합치기(Concat): 두 연결 리스트를 합치는 것 O(1) or O(n)

- 참조(Access): 연결 리스트에서 특정 인덱스에 있는 노드의 값을 반환하는 것 O(n)

---

양방향 연결 리스트(Doubly Linked List)

- 각 노드는 다음 노드와 이전 노드를 가리키는 포인터(next 포인터, prev 포인터)를 모두 가지고 있다.
- 첫 번째 노드와 마지막 노드를 모두 알 수 있다.

 

1) 양방향 연결리스트 단점

- 단방향 연결 리스트보다 메모리 사용량이 높다.

- 메모리가 제한적인 환경에서는 단방향 연결리스트보다 성능이 떨어질 수 있다.

- 단방향 연결 리스트보다 구현이 복잡하다.

---

더미 노드를 사용하는 이유

- 더미 노드를 사용하면 연결 리스트의 코드가 더 간결하고 쉽게 유지보수할 수 있다.

- 사용법:

리스트의 맨 앞에 새로운 노드를 삽입할 때, 더미 노드 다음에 새로운 노드를 삽입한다.

이렇게 하면 특별한 경우를 처리하지 않고도 리스트의 시작점에서 노드를 추가하거나 삭제할 수 있다.

또한, 더미 노드를 사용하면 연결 리스트가 비어있는 경우와 비어있지 않은 경우를 구분할 필요가 없다.

빈 리스트에서 노드를 삭제하려는 경우, 더미 노드 다음에 노드가 없으므로 삭제를 하지 않고 그냥 반환하면 된다.

따라서, 더미 노드를 사용하면 리스트의 시작점과 끝점을 추적하는 데 필요한 조건문을 제거할 수 있다.

이로 인해 코드의 가독성이 높아지며, 예외 처리가 단순화되어 코드의 안정성도 높아진다.

---

스택

- 가장 기본적인 자료 구조 중 하나로, 데이터를 일시적으로 저장하거나 처리하기 위해 사용된다.

- 스택은 후입선출-LIFO(Last-In-First-Out)의 원칙에 따라, 가장 마지막에 추가된 데이터가 가장 먼저 꺼내지는 자료 구조다.
- 스택은 일반적으로 push(삽입)와 pop(삭제) 두 가지 연산을 지원한다.

* push 연산은 스택의 맨 위에 데이터를 삽입하는 연산이며 pop 연산은 스택의 맨 위에서 데이터를 삭제하는 연산

def is_valid_expression(expr):
    stack = []  # 스택을 생성

    for ch in expr:  # 수식에서 문자를 하나씩 읽기
        if ch == '(':  # 문자가 '('이면 스택에 push
            stack.append(ch)
        elif ch == ')':  # 문자가 ')'이면 스택에서 pop하여 '('가 있었는지 확인
            if not stack:  # 스택이 비어있으면 괄호의 쌍이 유효하지 않은 것
                return False
            stack.pop()

    if stack:  # 모든 문자를 읽어들인 후, 스택에 남아있는 '('의 개수가 있는지 확인
        return False  # 스택에 '('가 남아있으면 괄호의 쌍이 유효하지 않은 것
    else:
        return True  # 스택이 비어있다면, 괄호의 쌍이 유효한 것

 

1) 수식의 후위 표기법

- 중위 표기법(infix notation): 연산자가 피연산자들의 사이에 위치

ex) (A+B) * (C+D)

- 후위 표기법(postfix notation): 연산자가 피연사자들의 뒤에 위치

ex) AB+CD+*

 

2) 표현식의 변환

- 중위 표현식 -> 후위 표현식

ex) A+B*C -> ABC*+, A*B+C -> AB*C+

- (괄호) 중위 표현식 -> 후위 표현식

ex) (A+B)*C -> AB+C*, A*(B+C) -> ABC+*

- (이중 괄호) 중위 표현식 -> 후위 표현식

ex) (A+B)*(C+D) -> AB+CD+*, (A+(B-C))*D -> ABC-+D*, (A*(B-(C+D)) -> ABCD+-*

---

어려웠던 점

1) 연결 리스트 자료 구조의 포인터에 대해 흐름을 이해

2) 더미 데이터가 들어가니 head와 tail 데이터 지정

3) 스택이 쌓이고 나가는 과정