연결 리스트(Linked list)와 스택(Stack)

연결 리스트 (Linked List)

• 다른 추상 자료형을 구현할 때 기반이 되는 기초 선형 자료구조
• 선형 배열과 비슷하지만, 링크라고 부르는 고리로 원소리들이 연결되는 점이 다르다
• 장점
  • 원소를 삽입, 삭제하는 것이 쉬움 (빠름)
• 단점
  • 데이터 구조 표현에 소요되는 저장 공간(메모리) 소요가 크다
  • k 번째 원소를 찾는데 배열보다 시간이 오래 걸림
    (배열은 데이터 원소들이 번호가 있는 칸에 있지만, 연결 리스트는 연결된 형태)
• 종류
  • 단방향 연결 리스트 (Singly Linked List)
  • 양방향 연결 리스트 (Doubly Linked Lists)
  • 원형 연결 리스트 (Circular Linked List)

---

 

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

• 노드들이 앞/뒤로 연결되어 있음
  (인접한 두 개의 노드가 앞의 노드로부터 뒤의 노드가, 뒤의 노드로부터 앞의 노드로 연결)
• 리스트의 맨 앞과 맨 뒤에 .더미 노드(dummy node)를 하나씩 추가 가능
• 장점
  • 데이터 원소를 차례로 방문할 때, 앞에서부터 뒤로도 가능하지만 뒤에서부터 앞으로도 가능
    (컴퓨터 운영체제(operating system)에서 리스트를 대상으로 앞/뒤로 왔다 갔다하는 작업이 많아 용이)
• 단점
  • 링크를 나타내기 위한 메모리 사용량 증가
  • 원소의 삽입/삭제하는 연산에 있어 복잡(프로그래머가 귀찮아짐)

---

스택 (Stack)

• 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료구조
• 후입선출 (LIFO - Last in First Out) 자료구조
• 스택에 데이터를 추가하는 동작 = 푸시 (push)
• 마지막에 추가되었던 원소를 꺼내고 삭제하는 동작 = 팝 (pop)
• 기초 연산 동작
  • size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
  • isEmpty() : 현재 스택이 비어 있는지를 판단
  • push(x) : 데이터 원소 x를 스택에 추가
  • pop() : 스택에 가장 나중에 저장된 데이터 원소를 반환하고 제거
  • peek() : 스택에 가장 나중에 저장된 데이터를 반환하고 제거하지 않음