2026.10.13 · 5분 읽기 · 조회 0
리스트는 가장 자유로운 선형 자료구조이다.
Stack, Queue, Deque 와의 차이점 : 자료의 접근 위치

ADT는 "무엇을 하는가"를 알려주는 논리적 모델이다. 리스트를 통해 위와 같은 연산들을 수행할 수 있다.
O(1) 이다.O(N) 이다.
파이썬 리스트는 스마트한 배열이다.
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)
-> 맨 뒤냐 아니냐에 따라 시간복잡도가 나뉜다.
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)클래스로 구현하는 것이 더 좋은 방법이다.
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는 이제 전역변수가 아니라 객체마다 하나씩 생기는 멤버 변수이다.
객체를 여러개 만들어 독립적인 리스트를 동시에 쓸 수 있다.
라인 편집기 기능 (메뉴)
라인 삽입, 행 번호와 문자열 입력하면 행에 한 라인 추가한 라인 삭제. 행 번호를 입력하면 그 행을 삭제한 라인 변경. 행 번호와 문자열을 입력하면 그 행의 내용을 변경현재 내용 출력. 현재 문서의 모든 내용을 라인 번호와 함께 출력파일 입력. 지정된 파일로부터 라인을 읽어 들임
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에 저장됩니다.