[자료구조] 선형 리스트 (Linear List)

선형 리스트란?

• 데이터를 일정한 순서로 나열한 구조
• 순차 리스트(Ordered List)라고도 한다.
• 입력순으로 저장하는 데이터에 적당한 구조다.

---

선형 리스트의 연산

1. 선형 리스트 생성(데이터 추가) 함수
2. 데이터 삽입 함수
3. 데이터 삭제 함수

---

선형리스트의 구현

선형리스트를 쇼핑 장바구니에 비유하여 코드로 구현해보았다.

1. 데이터 추가 함수

basket = []   # 빈 리스트 생성

def add_data(grocery):    # 데이터 추가를 위한 함수

    basket.append(None) 
    blen = len(basket)
    basket[blen - 1] = grocery
    
add_data("사과")
add_data("당근")
add_data("감자")
add_data("딸기")
add_data("양파")

print(basket)

 

basket 이라는 빈 리스트(장바구니)를 선언한다. 그 이후 add_data() 함수를 통해

 

데이터의 추가를 구현한다. 우선 리스트의 맨 뒤에 None값을 추가시킨 후

 

그 자리에 자료를 채워 넣는 방식으로 구현한다.

 

<--- 결과 --->

['사과', '당근', '감자', '딸기', '양파']

---

2. 데이터 삽입 함수

basket = ["사과", "당근", "감자", "딸기", "양파"]

def insert_data(position, grocery):
    if position < 0 or position > len(basket):    # IndexError 예외처리
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return

    basket.append(None)
    blen = len(basket)

    for i in range(blen - 1, position, -1):  # 뒤에서부터 position까지 차례대로
        basket[i] = basket[i - 1]            # 앞에서 뒤로 1칸씩 이동
        basket[i - 1] = None

    basket[position] = grocery
    
insert_data(1, '토마토')
print(basket)
insert_data(8, '피망')
print(basket)
insert_data(4, '배추')
print(basket)

여러 자료가 들어있는 리스트에 데이터를 삽입할 수 있는 insert_data() 함수를 구현한다.

 

우선 데이터를 삽입할 위치가 basket의 크기 범위를 벗어나면 예외처리를 해준다.

 

for문을 통해 리스트의 맨 뒤부터 position까지 한 칸씩 뒤로 이동하며 None을 position까지 가져온다.

 

이후 None 자리에 자료를 삽입한다.

 

<--- 결과 --->

['사과', '토마토', '당근', '감자', '딸기', '양파']
데이터를 삽입할 범위를 벗어났습니다.
['사과', '토마토', '당근', '감자', '딸기', '양파']
['사과', '토마토', '당근', '감자', '배추', '딸기', '양파']

---

3. 데이터 삭제 함수

basket = ["사과", "당근", "감자", "딸기", "양파"]

def delete_data(position):                       # 데이터 제거 함수
    if position < 0 or position > len(basket):   # IndexError 에외처리
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return

    blen = len(basket)
    basket[position] = None

    for i in range(position + 1, blen):    # position까지 뒤에서부터 한 칸씩 이동
        basket[i - 1] = basket[i]
        basket[i] = None

    del(basket[blen - 1])
    
delete_data(1)
print(basket)
delete_data(5)
print(basket)
delete_data(2)
print(basket)

여러 자료가 들어있는 리스트의 자료를 삭제하는 delete_data() 함수를 구현한다.

 

앞선 insert_data() 함수와 마찬가지로 IndexError 예외처리 이후

 

position 위치의 값을 None으로 변경 후, position까지 한 칸씩 자료들을 앞으로 이동시킨다.

 

마지막으로 basket의 비어있는 맨 뒤 한 칸을 del()을 통해 제거해준다.

 

<--- 결과 --->

['사과', '감자', '딸기', '양파']
데이터를 삭제할 범위를 벗어났습니다.
['사과', '감자', '딸기', '양파']
['사과', '감자', '양파']

---

전체 코드

def add_data(grocery):  # 데이터 추가를 위한 함수

    basket.append(None)
    blen = len(basket)
    basket[blen - 1] = grocery

def insert_data(position, grocery):
    if position < 0 or position > len(basket):    # IndexError 예외처리
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return

    basket.append(None)
    blen = len(basket)

    for i in range(blen - 1, position, -1):  # 뒤에서부터 position까지 차례대로
        basket[i] = basket[i - 1]            # 앞에서 뒤로 1칸씩 이동
        basket[i - 1] = None

    basket[position] = grocery

def delete_data(position):                       # 데이터 제거 함수
    if position < 0 or position > len(basket):   # IndexError 에외처리
        print("데이터를 삭제할 범위를 벗어났습니다.")
        return

    blen = len(basket)
    basket[position] = None

    for i in range(position + 1, blen):    # position까지 뒤에서부터 한 칸씩 이동
        basket[i - 1] = basket[i]
        basket[i] = None

    del(basket[blen - 1])

## 전역 변수 선언 부분 ##
basket = []
select = -1 # 1: 추가, 2: 삽입, 3: 삭제, 4: 종료

## 메인코드 부분 ##
if __name__=="__main__":

    while(select != 4):
        select = int(input("선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->"))
        if (select==1):
            data = input('추가할 데이터--> ')
            add_data(data)
            print(basket)
        elif (select==2):
            pos = int(input('삽입할 위치--> '))
            data = input('추가할 데이터--> ')
            insert_data(pos, data)
            print(basket)
        elif (select==3):
            pos = int(input('삭제할 위치--> '))
            delete_data(pos)
            print(basket)
        elif (select==4):
            print(basket)
            exit
        else:
            print('1~4 중 하나를 입력하세요.')
            continue

 

<--- 결과 --->

선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->1
추가할 데이터--> 감자
['감자']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->1
추가할 데이터--> 마늘
['감자', '마늘']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->1
추가할 데이터--> 피망
['감자', '마늘', '피망']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->2
삽입할 위치--> 1
추가할 데이터--> 대파
['감자', '대파', '마늘', '피망']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->3
삭제할 위치--> 3
['감자', '대파', '마늘']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->4
['감자', '대파', '마늘']