[Python] 선형 연결 리스트(Linear Linked List)

선형 리스트(Linear Linked List)

선형 리스트의 기본

개념

• 데이터를 일정한 순서로 나열한 구조
• 순차 리스트(Ordered List)라고도 한다.
• 입력 순서대로 저장하는 데이터에 해당한다.
• 선형 리스트는 다양한 방법으로 구현할 수 있지만, 가장 기본적인 방법은 배열 을 이용하는 것이다.
• 선형 리스트는 메모리에서도 차례로 저장된다.

 

원리

데이터 삽입

• 1단계 : 맨 끝에 빈칸을 확보한다.
• 2단계 : 삽입하고자 하는 공간에 빈칸이 없으므로, 삽입하고자 하는 공간 뒤에 있는 요소들을 한칸씩 뒤로 옮긴다.
• 3단계 : 빈자리에 요소를 삽입한다.

 

데이터 삭제

• 원하는 요소가 삭제된 후 빈칸을 그대로 두지 않고 뒤의 요소들을 앞으로 한칸씩 이동시킨다.

 

 

선형 리스트의 구현

• 사용자가 입력하는 데이터가 가변적으로 작동하는 범용적인 코드를 작성해 보자.

 

① 리스트 생성

katok = []    # 빈 배열

def add_data(friend) :
    katok.append(None)
    kLen = len(katok)
    katok[kLen-1] = friend

 

② 데이터 삽입

중간 데이터 삽입

katok.append(None)

for 현재위치 in range(마지막위치, 지정위치, -1) :
    katok[현재위치] = katok[현재위치-1]
    katok[현재위치-1] = None
    
katok[지정위치] = 요소

 

맨 끝 데이터 삽입

katok.append(None)

for 현재위치 in range(마지막위치, 지정위치, -1) :    # 어차피 작동하지 않음.
    katok[현재위치] = katok[현재위치-1]
    katok[현재위치-1] = None

katok[지정위치] = friend

 

함수 완성

katok = ['다현', '정연', '쯔위', '사나', '지효']

# 선형 리스트에 데이터를 삽입하는 함수
def insert_data(position, friend):
    if position < 0 or position > len(katok):
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return
    
    katok.append(None)          # 빈칸 추가
    kLen = len(katok)           # 배열의 현재 크기

    for i in range(kLen - 1, position, -1):
        katok[i] = katok[i - 1]
        katok[i - 1] = None

    katok[position] = friend    # 지정한 위치에 친구 추가

# 사용 예
insert_data(2, '솔라')
insert_data(6, '문별')

 

③ 데이터 삭제

중간 데이터 삭제

katok[지정위치] = None

for 현재위치 in range(지정위치+1, 마지막위치+1) :
    katok[현재위치-1] = katok[현재위치]
    katok[현재위치] = None

delete(katok[지정위치])

 

맨 마지막 데이터 삭제

katok[지정위치] = None

for 현재위치 in range(지정위치+1, 마지막위치+1) :
    katok[현재위치 - 1] = katok[현재위치]
    katok[현재위치] = None
    
del(katok[지정위치])

 

함수 완성

katok = ['다현', '정연', '쯔위', '사나', '지효']

# 선형 리스트에서 데이터를 삭제하는 함수
def delete_data(position):
    if position < 0 or position > len(katok):
        print("데이터를 삭제할 범위를 벗어났습니다.")
        return
    
    kLen = len(katok)
    katok[position] = None      # 데이터 삭제

    for i in range(position + 1, kLen):
        katok[i - 1] = katok[i]
        katok[i] = None         # 배열의 맨 마지막 위치 삭제
    
    del(katok[kLen - 1])

# 사용 예
delete_data(1)
delete_data(3)

 

선형 리스트의 완성

## 함수 선언 부분 ##
def add_data(friend):
    katok.append(None)
    kLen = len(katok)
    katok[kLen - 1] = friend

# 선형 리스트에 데이터를 삽입하는 함수
def insert_data(position, friend):
    if position < 0 or position > len(katok):
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return
    
    katok.append(None)          # 빈칸 추가
    kLen = len(katok)           # 배열의 현재 크기

    for i in range(kLen - 1, position, -1):
        katok[i] = katok[i - 1]
        katok[i - 1] = None

    katok[position] = friend    # 지정한 위치에 친구 추가

# 선형 리스트에서 데이터를 삭제하는 함수
def delete_data(position):
    if position < 0 or position > len(katok):
        print("데이터를 삭제할 범위를 벗어났습니다.")
        return
    
    kLen = len(katok)
    katok[position] = None      # 데이터 삭제

    for i in range(position + 1, kLen):
        katok[i - 1] = katok[i]
        katok[i] = None         # 배열의 맨 마지막 위치 삭제
    
    del(katok[kLen - 1])

## 전역 변수 선언 부분 ##
katok = []
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(katok)
        elif (select == 2):
            pos = int(input("삽입할 위치--> "))
            data = input("추가할 데이터--> ")
            insert_data(pos, data)
            print(katok)
        elif (select == 3):
            pos = int(input("삭제할 위치--> "))
            delete_data(pos)
            print(katok)
        elif (select == 4):
            print(katok)
            exit
        else:
            print("1~4 중 하나를 입력하세요.")
            continue

 

선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 1
추가할 데이터--> Apple
['Apple']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 1
추가할 데이터--> Banana
['Apple', 'Banana']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 1
추가할 데이터--> Tomato
['Apple', 'Banana', 'Tomato']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 2
삽입할 위치--> 1
추가할 데이터--> Melon
['Apple', 'Melon', 'Banana', 'Tomato']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 2
삽입할 위치--> 3
추가할 데이터--> Kiwi
['Apple', 'Melon', 'Banana', 'Kiwi', 'Tomato']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 3
삭제할 위치--> 4
['Apple', 'Melon', 'Banana', 'Kiwi']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)--> 4
['Apple', 'Melon', 'Banana', 'Kiwi']