[Algorithm] 자료구조와 알고리즘 - 1. 자료구조 - 선형 리스트

이 포스팅은 <파이썬 자료구조와 알고리즘 for beginner> 를  학습하면서 정리한 내용이다.

https://www.yes24.com/Product/Goods/97142842

파이썬 자료구조와 알고리즘 for Beginner - 예스24

 

 

자료구조

컴퓨터 프로그래밍 언어에서 효율적인 자료의 형태,
저자의 표현에 따르면 자료구조 : 식재료, 알고리즘 : 요리

---

01. 자료구조의 종류

 

파이썬 자료구조와 알고리즘 for beginner ch01

 

선형 자료구조(실무 활용도 높음)

---

• 리스트
  • 선형 리스트(= 순차 리스트) : 배열
  • 단순 연결 리스트 : 노드(Data + Link)
  • 원형 연결 리스트 : 꼬리가 다시 머리
• 스택 :  한쪽이 막힌 파이프
  • Push, pop, top
• 큐
  • 순차 큐( = 일반 큐)
  • 원형 큐( = 환형 큐)

 

 

비선형 자료 구조(시험용)

---

• 트리
  • 이진트리
• 그래프
  • 개념

 

---

02. 선형 자료구조

데이터를 한 줄로 순차적으로 표현한 형태
선형 리스트, 연결 리스트, 스택 , 큐 등이 해당함

https://goodgid.github.io/DS-Linear-and-NonLinear/

 

---

 

03. 선형 리스트

데이터를 일정한 순서로 나열한 자료구조
입력 순서대로 저장

예시를 통해서 이해해보자.

---

카톡으로 연락 온 친구를 배열을 이용하여 표현하는 코드 구현

- 연락 많이 온 순서대로 배열

- 다현 > 정연 > 쯔위 > 사나 > 지효

 

01 ) 단순 구현

## 함수 선언부


## 전역 변수부
katok = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드부
print(katok)

## 데이터 추가 (모모에게 카톡 1회)
# 1단계 : 빈칸 추가
katok.append(None)
# 2단계 : 마지막 칸에 데이터 넣기
katok[5] = '모모'
print(katok)

## 데이터 삽입 (미나에게 카톡 40회 연속) --> 미나가 3등
# 1단계 : 빈칸 추가
katok.append(None)
# 2단계 : 한칸씩 옆으로 이동(반복)
katok[6] = katok[5]
katok[5] = None
katok[5] = katok[4]
katok[4] = None
katok[4] = katok[3]
katok[3] = None
# 3단계 : 데이터 입력
katok[3] = '미나'
print(katok)

## 데이터 삭제 (사나가 카톡 차단) --> 4등 삭제
# 1단계 : 지우기
katok[4] = None
# 2단계 : 1칸씩 앞으로 이동.. 마지막 친구까지
katok[4] = katok[5]
katok[5] = None
katok[5] = katok[6]
katok[6] = None
# 3단계 : 빈칸 제거
del(katok[6])
print(katok)

 

02) 선형 리스트 형태로 구현

## 함수 선언
def add_data(freind): # 데이터 추가
    # 1단계 : 빈칸 추가
    katok.append(None)
    klen = len(katok)
    # 2단계 : 데이터 입력
    katok[klen - 1] = freind

def insert_data(position, friend): # 데이터 삽입
    # 1단계 : 빈칸 추가
    katok.append(None)
    klen = len(katok)
    # 2단계 : 한칸씩 이동
    ## katok(klen -1) = katok(klen - 2)
    for i in range(klen -1, position, -1): # 핵심 어려움
        katok[i] = katok[i-1]
        katok[i-1] = None

    # 3단계 : 데이터 입력
    katok[position] = friend

def delete_data(position): # 데이터 삭제
    # 1단계 지우기
    katok[position] = None
    klen = len(katok)
    # 2단계 : 한칸씩 당기기
    for  i in range(position + 1, klen,1): # 핵심
        katok[i-1] = katok[i]
        katok[i] = None
    # 3단계 : 마지막 칸을 제거
    del(katok[klen - 1])


## 전역 변수 선언
katok = []

## 메인 
add_data('다현')
add_data('정연')
add_data('쯔위')
add_data('사나')
add_data('지효')
print(katok)
add_data('모모')
print(katok)
insert_data(3,'미나')
delete_data(4) # 위치만 넘겨 주기
print(katok)