Week2 - 2

Linked List

종류

• Linked List(단순 연결 리스트)
• Doubly Linked List(양방향 연결 리스트)
• Circular Linked List(원형 연결 리스트)

주요 개념

• 노드 : 데이터와 다음 노드를 가리키는 포인터로 이루어진 구조체이다.
            양방향, 원형 연결 리스트는 이전 노드를 가리키는 포인터도 가지고 있음.
• head : 연결 리스트의 맨 앞
• tail : 연결 리스트의 맨 뒤
• nodeCount : 연결 리스트의 사이즈
• 추가/삽입 : 삽입하려는 위치의 노드(A)와 그 다음 노드(B)가 있다.
                   A 노드의 다음 노드는 삽입하는 노드. 삽입하는 노드의 다음 노드는 B노드가 된다.
                   양방향 연결 리스트는 삽입하는 노드의 이전 노드는 A 노드, B 노드의 이전 노드를 삽입하는 노드로 설정이 필요하다.
                   (Head, Tail)더미 노드를 사용하지 않는 경우 삽입하려는 위치에 따라 Head와 Tail의 재정의가 필요할 수 있다.
  • 필요한 예외 처리
    불가능한 위치에 노드 삽입
• 삭제/제거 : 제거하려는 노드의 위치와 그 이전 노드(A), 그 다음 노드(B)가 있다.
                   A 노드의 다음 노드는 B가 된다.
                   양방향 연결 리스트의 경우 B 노드의 이전 노드는 A가 된다.
                   제거하려는 위치에 따라 Head와 Tail 정보를 재정의할 필요가 있다.
  • 필요한 예외 처리
    연결 리스트가 비어있을 경우, 불가능한 위치의 노드 제거
• 열람 : head부터(양방향 연결 리스트에서는 사이즈의 절반 부터 tail까지) 해당 위치까지 이동 후 데이터 return
• 두 연결 리스트 합치기 : 앞 연결 리스트(A), 뒤 연결 리스트(B)
                                     A 리스트의 Tail 이전 노드의 다음 노드는 B 리스트 Head의 다음 노드.
                                     B 리스트 Head의 다음 노드의 이전 노드는 A리스트의 Tail 노드의 이전 노드.
                                     A 리스트의 Tail의 이전 노드는 B 리스트의 Tail의 이전 노드로 재정의.
  
  • 필요한 예외 처리
    A가 비어있을 경우, B가 비어있을 경우

 

Stack

특징

• LIFO(Last In First Out)

주요 개념

• size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 스택이 비어 있는지를 판단
• push(x): 데이터 원소 x 를 스택에 추가
• pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거
• top(), peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조

활용

• 재귀 함수
• 후위표현 수식 및 계산