chorock.page
소개글시리즈프로젝트실험
© 2026 chorock.page
← 목록으로
자료구조 · 2/5
← 이전 글다음 글 →
python자료구조

리스트(List) : ADT, Array, Linked-List

2026.10.13 · 5분 읽기 · 조회 0

목차
리스트List ADT리스트의 구현배열구조(Array)연결된 구조(Linked-List)파이썬 리스트동적 배열시간 복잡도배열로 구현한 리스트함수 버전클래스 버전리스트의 응용 : 라인 편집기

리스트

리스트는 가장 자유로운 선형 자료구조이다.

  • 순서를 가진 항목들의 모임
  • 앞에서부터 0번, 1번... n-1번 항목을 가진다
  • Stack, Queue, Deque 와의 차이점 : 자료의 접근 위치

List ADT


ADT는 "무엇을 하는가"를 알려주는 논리적 모델이다. 리스트를 통해 위와 같은 연산들을 수행할 수 있다.

리스트의 구현

배열구조(Array)

  • 구현이 간단하다
  • 각 항목에 대한 접근이 O(1) 이다.
  • 삽입 삭제 시 오버헤드가 있다.
  • 항목의 개수 제한이 있다.

연결된 구조(Linked-List)

  • 구현이 복잡하다.
  • 항목 접근이 O(N) 이다.
  • 삽입, 삭제가 효율적이다.
  • 크기가 제한되지 않는다.
  • 파이썬 리스트: C언어의 배열이 진화된 스마트한 배열이다. 해당 글에서는 배열 또는 배열 구조의 의미로 사용한다.
  • 연결 리스트: 자료들이 일렬로 나열할 수 있는 구조를 말한다. 배열구조(파이썬의 리스트)에 대응되는 다른 수단이다.
  • 자료구조 리스트: 추상적인 의미의 리스트를 의미한다. ADT의 구현 대상을 의미한다.

파이썬 리스트

파이썬 리스트는 스마트한 배열이다.

python
A = [1,2,3,4,5]  # 파이썬 리스트 A
 
int A[5] = {1,2,3,4,5};  # C언어의 배열 선언

C의 int A[5]는 크기가 5로 고정된다.
그러나 파이썬의 A = [1,2,3,4,5] 는 append, insert 로 계속 늘어날 수 있다.
용량이 알아서 늘어나기 때문에 스마트한 배열이라고 부른다.

동적 배열

  • 파이썬의 리스트는 동적배열로 구현되었다.
  • 필요한 양보다 넉넉한 크기의 메모리를 사용한다.
    우측의 경우에는 빈칸이 없다.

때문에 추가적인 공간이 필요하면 기존 메모리를 버리고 더 큰 새로운 메모리를 할당해서 사용한다.
핵심은 기존 메모리를 늘리는게 아니라 새로 할당해서 통째로 옮긴다는 것이다.

해당 복사는 O(N)이지만 용량이 찰 때만 가끔 일어나기 때문에 append는 대부분의 경우 O(1)이 된다.

시간 복잡도

  • append(e) 연산 : 대부분의 경우 O(1)

  • pop()연산 : O(1)

  • insert(pos, e) 연산: O(n)

  • pop(pos) 연산 : O(n)
    -> 맨 뒤냐 아니냐에 따라 시간복잡도가 나뉜다.

배열로 구현한 리스트

함수 버전

python
items = []                             # 리스트 항목 저장을 위한 파이썬 리스트        # 전역변수
def insert(pos, elem) :                # pos 위치에 새로운 요소 item을 삽입한다.
    items.insert(pos, elem)            # 파이썬 리스트 클래스의 insert 연산
def delete(pos) :                      # pos 위치에 있는 요소를 꺼내고 반환한다.
    return items.pop(pos)              # 파이썬 리스트 클래스의 pop 연산
def getEntry(pos): return items[pos]   # pos번째 항목 반환
 
def isEmpty( ): return len(items) == 0  # 크기가 0이면 True 아니면 False
def size( ): return len(items)          # 리스트의 크기 반환. len()함수 이용
def clear( ):  global items; items = []      # items를 초기화
def find(item) : return items.index(item)   # 탐색 후 인덱스 반환
def replace(pos, elem): items[pos] = elem   # pos번째 항목 변경
def sort( ) : items.sort()             # 정렬(sort메소드 이용)
def merge(lst) : items.extend(lst)     # 병합(확장)
def display(msg='ArrayList:' ):        # 출력: 디폴트 인수 사용
    print(msg, size(), items)          # 메시지+크기+배열내용 출력

items = [] 를 전역변수로 두고 ADT의 각 연산을 함수 하나씩으로 옮긴다.

  • insert(), delete() : 최악의 경우 O(n)
  • getEntry() : O(1)

클래스 버전

클래스로 구현하는 것이 더 좋은 방법이다.

python
class ArrayList:
    def __init__(self):                 # 생성자 
        self.items = []                 # 멤버 변수 선언 및 초기화
 
    def insert(self, pos, elem) :
        self.items.insert(pos, elem)
 
    def delete(self, pos) :        # if pos >= len(self.items) : return
        return self.items.pop(pos)
 
    def isEmpty(self):
        return self.size() == 0
 
    def getEntry(self, pos) :
        return self.items[pos]
 
    def size(self):
        return len(self.items)
 
    def clear(self) :
        self.items = []             # items는 전역변수가 아니고 클래스의 멤버변수
    
    def find(self, item) :
        return self.items.index(item)
 
    def replace(self, pos, elem) :
        self.items[pos] = elem
 
    def sort(self) :
        self.items.sort()
 
    def merge(self, lst) :                 
        self.items.extend(lst)           
 
    def display(self, msg='ArrayList:' ):
        print(msg, '항목수=', self.size(), self.items)

items는 이제 전역변수가 아니라 객체마다 하나씩 생기는 멤버 변수이다.
객체를 여러개 만들어 독립적인 리스트를 동시에 쓸 수 있다.

리스트의 응용 : 라인 편집기

  • 라인 단위로 입력이나 삭제를 할 수 있는 문서 편집기
  • 리스트로 구현하며 한 줄의 문자열이 리스트의 하나의 항목이 됨

라인 편집기 기능 (메뉴)

  • i : 라인 삽입, 행 번호와 문자열 입력하면 행에 한 라인 추가
  • d : 한 라인 삭제. 행 번호를 입력하면 그 행을 삭제
  • r : 한 라인 변경. 행 번호와 문자열을 입력하면 그 행의 내용을 변경
  • p : 현재 내용 출력. 현재 문서의 모든 내용을 라인 번호와 함께 출력
  • l : 파일 입력. 지정된 파일로부터 라인을 읽어 들임
  • q : 종료
python
def myLineEditor():
    listA= ArrayList()
    while True:
        command=input('i-입력 d-삭제 r-변경 p-출력 l-파일읽기 s-파일저장 q-종료:')
 
        if command == 'q' : return
 
        elif command == 'i':
            pos =int(input('입력할 행번호 : '))
            str1 = input('입력 내용 :')
            listA.insert(pos, str1)
 
        elif command == 'd':
            pos =int(input('삭제할 행번호 : '))
            listA.delete(pos)
 
        elif command == 'r':
            pos =int(input('수정할 행번호 : '))
            str1 = input('수정 내용 :')
            listA.replace(pos, str1)
 
        elif command == 'p':
            print('Line Editor')
            for line in range(listA.size()):
                print('[{:2d}] '.format(line), end="")
                print(listA.getEntry(line))
            print()
 
        elif command == 'l':
            infile = open('test.txt', 'r')
            lines = infile.readlines()
            for line in lines:
                listA.insert(listA.size(), line.rstrip())
            infile.close()
 
        elif command == 's':
            outfile = open('test.txt', 'w')
            for i in range(listA.size()):
                outfile.write(listA.getEntry(i)+'\n')
            outfile.close()
 
#함수 myLineEditor() 선언 끝 :
 
myLineEditor() #함수 호출
초록
초록

앱과 웹을 만들고, 직접 운영하며 기록합니다.

댓글

giscus로 동작하며 GitHub Discussions에 저장됩니다.

관련 글

자료구조자료구조python

연결된 구조(LinkedList)

2026.11.17·7분 읽기·조회 0
자료구조python자료구조

큐(queue) - ADT, BFS

2026.10.16·4분 읽기·조회 0
자료구조python자료구조

스택(Stack) - ADT, 응용, DFS

2026.10.15·11분 읽기·조회 0

목차

리스트List ADT리스트의 구현배열구조(Array)연결된 구조(Linked-List)파이썬 리스트동적 배열시간 복잡도배열로 구현한 리스트함수 버전클래스 버전리스트의 응용 : 라인 편집기