선형 리스트 (Linear List)

-선형 리스트의 개념

선형 리스트는 데이터를 일정한 순서로 나열한 자료구조로, 순차 리스트라고도 한다. 선형 리스트는 입력 순서대로 저장하는 데이터에 적당하다. 예를 들면, 좋아하는 프로그래밍 언어 종류, 연락이 많이 온 친구 목록 등이 있다. 다양한 방법으로 구현할 수 있으나, 가장 기본적인 것은 배열(Array)을 이용하는 것이다. 

 

-선형 리스트의 원리

1. 데이터 삽입 : 빈칸 확보 -> 자리 이동 -> 데이터 삽입 

예. a - b - c 선형 리스트에 d를  b와 c 사이에 삽입? -> a - b - c - * (빈칸 확보) -> a - b - * - c (자리 이동) -> a - b - d - c (데이터 삽입)

 

2. 데이터 삭제 : 데이터 삭제 -> 자리 이동 -> 빈칸 제거

예. a - b - c - d 선형 리스트에서 b를 삭제? -> a - * - c - d (데이터 삭제) -> a - c - * - d -> a - c - d - * (자리 이동) -> a - c - d (빈칸 제거)

 

-기본 선형 리스트

* 선형 리스트 데이터 추가 함수 구현 부분

def add_data(value):
    # basicList에 None(빈) 공간 추가
    basicList.append(None)
    # basicLen 변수에 basicList의 길이(정수)만큼을 할당해줌
    basicLen = len(basicList)
    # basicList에서 길이-1 위치에 추가하고자 하는 값을 할당해줌
    basicList[basicLen-1] = value

* 선형 리스트 특정 위치 데이터 추가 함수 구현 부분

def insert_data(position, value):
    # 삽입하고자 하는 위치가 0보다 작거나 최대 길이를 벗어나면 예외 메시지 발생
    if position < 0 or position > len(basicList):
        print("범위를 벗어났습니다.")
        return
    
    # 초기 리스트에 빈 공간 추가
    basicList.append(None)
    # basicLen 변수에 현재 리스트의 길이(정수)를 할당
    basicLen = len(basicList)

    # 삽입 원리 (맨 뒤에 빈 공간 추가 -> 끝에 위치 부터 하나씩 우측으로 shift -> 원하는 삽입 위치 까지)
    # 따라서, 길이 끝에서 시작해서 지정 위치까지 한칸씩 줄여가면서 값 하나씩 이동
    for i in range(basicLen-1, position, -1):
        basicList[i] = basicList[i-1]
        basicList[i-1] = None
    # 지정 위치에 사용자 값 할당
    basicList[position] = value

* 선형 리스트 특정 위치 데이터 삭제 함수 구현 부분

def delete_data(position):
    if position < 0 or position > len(basicList):
        print("범위를 벗어났습니다.")
        return

    basicLen = len(basicList)
    basicList[position] = None # 데이터 삭제
    # 삭제 원리 (지정 위치 값 삭제 -> 지정 위치의 다음 값부터 왼쪽으로 shift -> 리스트 길이 만큼)
    # 따라서, 지정 위치에서 시작해서 리스트 끝까지 한칸씩 줄여가면서 값 하나씩 이동
    for i in range(position+1, basicLen):
        basicList[i-1] = basicList[i]
        basicList[i] = None

    # 배열 마지막 위치값 삭제
    del(basicList[basicLen-1])

* 전역 변수 선언 및 메인 코드 구현 부분

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