선형 리스트

개념

--> 데이터를 일정한 순서로 나열한 자료구조
--> 입력 순서대로 저장하는 데이터에 적당
--> 배열 사용
--> 선형 리스트는 메모리에서도 차례로 저장된다.

원리

1. 데이터 삽입

1) 배열 맨 끝 자리를 확보한다.
2) 삽입할 위치 기준 오른쪽 데이터들을 뒤로 한 칸씩 이동시킨다.
3) 빈 자리에 데이터를 삽입한다.

2. 데이터 삭제

1) 해당 데이터를 삭제한다.
2) 삭제한 데이터 기준 오른쪽 데이터들을 앞으로 한 칸씩 이동시킨다.
3) 배열 맨 끝 자리를 제거한다.

간단 구현

* ex) 데이터가 5개인 선형 리스트

1. 리스트 생성

katok = ['다현', '정연', '쯔위', '사나', '지효'] # 데이터가 5개인 리스트 생성

* 배열의 index는 0부터 시작한다.

print(katok[0]) # 다현

2. 데이터 삽입

1) 맨 뒤에 데이터를 삽입하는 경우
  리스트에 빈칸 추가 -> 빈칸에 해당 데이터 삽입

katok.append(None) # 리스트에 빈칸 추가
katok[5] = '모모' # 빈칸에 해당 데이터 삽입
# ['다현', '정연', '쯔위', '사나', '지효', 모모']

2) 중간에 데이터를 삽입하는 경우
  리스트에 빈칸 추가 -> 해당 데이터 위치 전까지 오른쪽으로 한 칸씩 데이터 이동 -> 빈칸에 해당 데이터 삽입

katok.append(None) # 리스트에 빈칸 추가
# ['다현', '정연', '쯔위', '사나', '지효', '모모', None]
katok[6] = katok[5] # 데이터 오른쪽으로 한 칸 옮기기
katok[5] = None # 빈 칸으로 만들기
katok[5] = katok[4]
katok[4] = None
katok[4] = katok[3]
katok[3] = None
# ['다현', '정연', '쯔위', 'None', '사나', '지효', '모모']
katok[3] = '미나' # 빈 칸에 해당 데이터 삽입하기
# ['다현', '정연', '쯔위', '미나', '사나', '지효', '모모']

3. 데이터 삭제

 해당 데이터 삭제 -> 이후 데이터들 왼쪽으로 한 칸씩 이동 -> 마지막 빈칸 제거

katok[4] = None # 데이터 삭제
katok[4] = katok[5] # 데이터 이동
katok[5] = None
katok[5] = katok[6]
katok[6] = None
del katok[6]
# ['다현', '정연', '쯔위', '미나', '지효', '모모'] '사나' 데이터 삭제

일반 구현

1. 선형 리스트 생성

1) 빈 배열 생성 (배열의 맨 끝 위치는 len(배열명) - 1 이다.)

katok = []                # 빈 배열 생성

2) 선형 리스트 생성 함수 생성

def add_data(friend):     # 선형 리스트 생성 함수
   katok.append(None)
   kLen = len(katok)
   katok[kLen-1] = friend
add_data('다현')
add_data('정연')
add_data('쯔위')
add_data('사나')
add_data('지효')

2. 데이터 삽입

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, position, -1): # 맨 뒤에서부터 해당 위치까지 반복
        katok[i] = katok[i-1]
        katok[i-1] = None
    katok[position] = friend

3. 데이터 삭제

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])

기본 선형 리스트 전체 코드

## 함수 선언 부분 ##
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)-1:
        print('범위를 벗어났습니다.')
        return
    kLen = len(katok)
    katok.append(None)
    for i in range(kLen, position, -1): # 한 칸 추가했으므로 kLen-1부터가 아닌 kLen 부터이다.
        katok[i] = katok[i-1]
        katok[i-1] = None
    katok[position] = friend
def delete_data(position):
    if position < 0 or position > len(katok)-1:
        print('범위를 벗어났습니다.')
        return
    katok[position] = None
    kLen = len(katok)
    for i in range(position+1, kLen):
        katok[i] = katok[i-1]
        katok[i] = None
    del (katok[kLen-1])
## 전역 변수 선언 부분 ##
katok = []
select = -1
## 메인 코드 선언 부분 ##
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