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

📌 현재 게시글의 개념과 코드는 이 책을 참고하여 정리하였습니다.

선형 리스트(Linear List)

선형 리스트(Linear List)는 데이터를 일정한 순서로 나열한 구조이다.

다른 말로 순차 리스트(Ordered List)라고도 한다.

선형 리스트는 입력 순서대로 저장하는 데이터에 적당하다.

예를 들어, 좋아하는 프로그래밍 언어 종류, 카톡으로 연락이 많이 오는 친구, 오늘 수업할 과목 등을 저장하기에 적당하다.

또한, 요즘 같은 시기에 코로나 검사를 받기 위해 선별 진료소에 줄을 선 경우도 해당된다.

선형 리스트는 다양한 방법으로 구현이 가능하지만, 가장 간단한 방법은 배열을 이용하는 것이다!

가장 많이 연락이 온 순서 = ['다현', '정연', '쯔위', '사나', '지효']

선형 리스트의 원리

선형 리스트의 원리를 알기 위해

• 선형 리스트 생성
• 데이터 삽입
• 데이터 삭제

의 순서대로 과정을 살펴보겠다.

1. 선형 리스트 생성 함수

katok = []

def add_data(friend):

    katok.append(None)
    klen = len(katok)
    katok[klen-1] = friend

add_data("다현")
add_data("정연")
add_data("쯔위")
add_data("사나")
add_data("지효")

print(katok)

katok이라는 빈 배열을 생성하고, 안에 데이터를 삽입할 수 있는 함수 add_data를 만든다.

데이터를 삽입한 뒤 katok을 호출하면

Out:

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

의 값이 나온다.

2. 데이터 삽입 함수

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, '솔라')
print(katok)
insert_data(6, '문별')
print(katok)
insert_data(9, '화사')
print(katok)

데이터 삽입 함수를 살펴보면 position은 위치이다. 리스트 내에서도 어느 위치에 데이터를 삽입할지 정해야 하기 때문이다.

friend 매개변수는 친구의 이름이다.

위치와 이름을 지정해주면 그 자리에 데이터가 삽입된다.

Out:

['다현', '정연', '솔라', '쯔위', '사나', '지효']
['다현', '정연', '솔라', '쯔위', '사나', '지효', '문별']
데이터를 삽입할 범위를 벗어났습니다.
['다현', '정연', '솔라', '쯔위', '사나', '지효', '문별']

3. 데이터 삭제 함수

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)
print(katok)
delete_data(3)
print(katok)

위 코드를 살펴보면 delete_data의 함수를 만들었다.

삭제할 위치를 지정해주면 None 값으로 바꾼 다음에 뒤에 있는 데이터들을 한 칸씩 자리를 이동한다.

중간에 데이터가 삭제되었다고 빈 공간으로 두면 안 되기 대문이다.

Out:

['다현', '쯔위', '사나', '지효']
['다현', '쯔위', '사나']

지효가 삭제되었다.

4. 완성 코드

def add_data(frined):
    katok.append(None)
    klen = len(katok)
    katok[klen-1] = frined

def insert_data(position, friend):
    if position < 0 or position > len(katok):
        # '<' not supported between instances of 'str' and 'int'
        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

Out:

선택하세요(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: 종료)-->2
삽입할 위치--> 0
추가할 데이터--> 문별
['문별', '다현', '하나', '정연', '쯔위']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->3
삭제할 위치--> 3
['문별', '다현', '하나', '쯔위']
선택하세요(1: 추가, 2: 삽입, 3: 삭제, 4: 종료)-->4
['문별', '다현', '하나', '쯔위']

여기까지 데이터를 일정한 순서로 나열한 자료구조로 입력 순서대로 저장하는 데이터에 적절한 선형 리스트를 살펴보았다.