선형 리스트

  • 개념

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

  • 원리

    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
           
    
     

좋은 웹페이지 즐겨찾기