연결리스트, 스택

데이터 엔지니어링 데브코스 Day 2

- 자료구조 및 알고리즘 풀기 2

 

🚀 연결 자료구조 방식 (Linked Data Structure)

• 순차 자료구조 방식에서 연산 시간 및 저장 공간에 대한 문제를 개선한 자료 표현 방식으로 연결 자료구조와 비순차 자료구조(Nonsequential Data Structure)가 있음
• 순차 자료구조 방식처럼 원소의 논리적 순서와 물리적 순서가 일치할 필요 X
  • 연속한 메모리 물리주소에 의해 원소 순서를 표현 X
  • 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해서 연결되는 방식이기 때문
  • 물리적 순서를 맞추기 위한 오버헤드 발생 X
• 순차 자료구조는 하나의 고정 크기 메모리 공간이 필요하지만, 연결 자료구조는 여러 개의 작은 공간을 연결하여 전체를 표현하기에 크기 변경이 유연하고 효율적 메모리 사용 가능
• 연결 자료구조 방식을 표현한 구조에는 연결 리스트가 있고, 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트로 나눌 수 있음

 

🚀 연결 리스트 (Linked List)

연결 리스트

• 연결 자료구조 방식으로 데이터 요소가 노드로 구성되고, 각 노드는 데이터와 다음 노드를 가리키는 Link(링크)를 포함
• 데이터 순서가 메모리에 연속적으로 저장 X
• 데이터 삽입 및 삭제가 빠르지만 특정 인덱스 접근에는 선형 탐색 필요
• 선형 배열은 데이터 접근이 빠르지만 삽입 및 삭제 시에는 데이터 이동이 필요하여 연산이 느림
• 연결 리스트는 동적 크기 조정이 되어 메모리 관리 유연하며, 삽입 및 삭제 연산의 비용이 일정
• 선형 배열은 크기가 고정되어 메모리 사용이 불필요하게 발생 가능하며, 삽입 및 삭제 연산에 따라 메모리 재할당이 필요할 수 있음

 

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

양방향 연결 리스트 (이중 연결 리스트)

• 연결 리스트는 앞으로만 연결되어 있었지만, 양방향 연결 리스트는 노드들이 앞/뒤로 연결
• 연결 리스트에 비해 링크가 더 생기므로 메모리 사용량 증가 및 원소 삽입/삭제 연산에서 더 복잡함

 

🚀 스택 (Stack)

스택

• 스택이란 쌓아올린다는 의미로써, 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조
• 스택은 top 이라고 정한 한 곳으로만 쌓을 수 있고, top으로만 접근하도록 제한하여 만든 자료구조
  • 삽입/삭제는 전부 top을 통해서만 가능하기에 top이 가리키고 있는 스택의 마지막 자료만 삭제 가능
• 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out) 구조를 가짐
• 삽입 연산 push, 삭제 연산 pop