[파이썬 자료구조] 05. 리스트

1. 리스트

 1) 줄 세워져 있는 데이터 or 죽 늘어선 데이터

 ex) 위시리스트, 버킷리스트, 블랙리스트

 2) ADT 리스트: '리스트는 대략 이런이러한 작업으로 구성된 자료구조다'라고 정의한 것

 3) 리스트 VS 배열

   -리스트는 융통성이 있고 배열보다 추상 레벨이 높지만 배열과 같은 엄격함은 없다. 

   -파이썬의 리스트는 하부가 배열로 구현

   -so, 배열이 갖는 단점을 상당 부분 가지고 있음(중간에 원소를 삽입하면 삽입한 원소 이후의 원소들을 모두 오른쪽으로 한 칸 씩 시프트해야 함, 확보해 놓은 배열 공간이 다 찼을 때 새로운 배열을 할당받아 기존의 배열 내용을 복사해야 함)

 

2. 배열 리스트

1) 리스트 작업 종류

insert(i, x)   🌗x를 리스트의 i번 원소로 삽입한다. (맨 앞자리는 0번)

append(x)    🌗원소 x를 리스트의 맨 뒤에 추가한다. 

pop(i)  🌗리스트의 i번 원소를 삭제하면서 알려준다. 

remove(x)    🌗리스트에서 (처음으로 나타나는) x를 삭제한다. 

index(x)    🌗원소 x가 리스트의 몇 번 원소인지 알려준다. 

clear()  🌗리스트를 깨끗이 청소한다. 

count(x)    🌗리스트에서 원소 x가 몇 번 나타나는지 알려준다. 

extend(a)  🌗리스트에 나열할 수 있는 객체(ex. 리스트) a를 풀어서 추가한다. 

copy()  🌗리스트를 복사한다. 

reverse()  🌗리스트의 순서를 역으로 뒤집는다. 

sort()  🌗리스트의 원소들을 정렬한다. 

 

2) 원소 삽입

 ① [1, 3, 5, 6, 7] -> a.insert(1, 'Mon') -> [1, 'Mon', 3, 5, 6, 7]

파이썬은 하나의 리스트에 여러 타입의 원소가 혼재할 수 있다. 

 ② [1, 3, 5, 6, 7] -> a.append('Mon') -> [1, 3, 5, 6, 7, 'Mon']

 

3) 원소 삭제

① [1, 3, 5, 6, 7] -> a.pop(3) -> [1, 3, 5, 7]

    [1, 3, 5, 6, 7] -> a.pop() -> [1, 3, 5, 6]

    [1, 3, 5, 6, 7] -> a.pop(-1) -> [1, 3, 5, 6]

*파이썬은 리스트를 원형, 즉 맨 앞자리와 맨 뒷자리가 연결되어 있다고 생각하기 때문에 pop()이나 pop(-1)의 경우 끝자리를 삭제한다. 

 삭제할 위치를 명시하는 경우

② [1, 3, 5, 6, 7] -> a.remove(5) -> [1, 3, 6, 7]

 삭제할 원소를 명시하는 경우

 

4) 기타 작업

① [1, 3, 5, 6, 7] -> a.index(5) -> 2

원소가 몇 번 자리에 있는지 알려준다. 

② [1, 3, 5, 6, 7] -> a.clear() -> []

리스트를 깨끗이 비운다.

③ [1, 3, 5, 6, 7] -> a.extend([10, 20]) -> [1, 3, 5, 7, 10, 20]

리스트에 나열 가능한 객체를 덧붙인다. 

④ [1, 3, 5, 6, 7] -> a.reverse() -> [7, 6, 5, 3, 1]

리스트의 순서를 뒤집는다. 

⑤ [2, 4, 1, 5, 7] -> a.sort() -> [1, 2, 4, 5, 7]

리스트를 정렬한다.

 

5) 파이썬 내장 리스트의 한계

① 원소 삽입 시 삽입하는 자리 오른쪽부터 끝까지 모든 원소를 한 칸씩 시프트해주는 부담

*삭제에서는 반대 방향으로 시프트가 발생

② 배열이 꽉 찬 상태에서 삽입시 시도될 때 새 배열에 원소들을 모두 복사해야 하는 부담

 

3. 연결 리스트

1) 배열의 공간 낭비를 피할 수 있는 자료구조

2) 원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따르기 때문

3) 연결 리스트의 노드는 원소를 저장하는 item 필드와 노드를 가리키는 next 필드로 구성된다. 

 -item 필드는 정수나 실수 같은 숫자 타입이나 복잡한 객체가 될 수 있다. 

 -next 필드는 다음 노드를 가리키는 링크(자바의 레퍼런스 reference, C언어의 포인터 pointer다.

 4) 연결 리스트의 객체 구조 

 -(a)는 연결 리스트의 기본 형태

 -첫 번째 노드를 가리키는 레퍼런스 __head가 있다. 

 -나머지 노드는 첫 번째 노드에서 링크를 따라 접근

 -맨 마지막 노드의 링크는 뒤에 더 이상 노드가 없다는 의미로 None값을 할당

 -(b)는 빈 연결 리스트

 -노드들을 조각조각 할당받은 공간끼리 링크로 연결

5) 연결 리스트의 첫 번째 노드에 대한 레퍼런스 필드 __head와 리스트에 들어 있는 원소의 총 수를 저장하는 필드 __numItems가 있다. 

6) 연결 리스트 작업 종류

__head    🌗첫 번째 노드에 대한 레퍼런스

__numItems    🌗연결 리스트에 들어 있는 원소의 총 수

insert(i,x)    🌗x를 연결 리스트의 i번 원소로 삽입한다. (맨 앞자리는 0번)

append(x)    🌗연결 리스트의 맨 뒤에 원소 x를 추가한다. 

pop(i)    🌗연결 리스트의 i번 원소를 삭제하면서 알려준다.

remove(x)    🌗연결 리스트에서 (처음으로 나타나는) x를 삭제한다. 

get(i)    🌗연결 리스트의 i번 원소를 알려준다. 

index(x)    🌗원소 x가 연결 리스트의 몇 번 원소인지 알려준다. 

isEmpty()    🌗연결 리스트가 빈 리스트인지 알려준다. 

size()    🌗연결 리스트의 총 원소 수를 알려준다. 

clear()    🌗연결 리스트를 깨끗이 청소한다. 

count(x)    🌗연결 리스트에서 원소 x가 몇 번 나타나는지 알려준다. 

extend(a)    🌗연결 리스트에 나열할 수 있는 객체(ex, 리스트, 튜플 등) a를 풀어서 추가한다. 
copy()    🌗연결 리스트를 복사해서 새 연결 리스트를 리턴한다. 

reverse()    🌗연결 리스트의 순서를 역으로 뒤집는다. 

sort()    🌗연결 리스트를 정렬한다. 

7) 원소 삽입

① 더미 헤드 노드가 없는 경우 ❌ 

if i == 0:
	newNode.item = x
	newNode.next=__head
    __head = newNode
    __numItems += 1
else:
	newNode.item = x
    newNode.next = prev.next
    prev.next =newNode
    __numItems += 1

 

② 더미 헤드 노드가 있는 경우 ⭕

 

newNode.item = x
newNode.next = prev.next
prev.next = newNode
__numItems += 1

8) 원소 삭제

① 더미 헤드 노드가 없는 경우 ❌ 

if i==0:
	__head.next = __head.next.next
    __numItems -= 1
else:
	prev.next = prev.next.next
    __numItems -= 1

② 더미 헤드 노드가 있는 경우 ⭕

prev.next= prev.next.next
__numItems -= 1

9) 기타 작업

get(i):
	if i>=0 and i<=__numItems - 1:
    	return __getNode(i).item
    else:
    	print("error in get(", i, ")")

__getNode(i):
	curr = __head
    for index in ragne(i+1):
    	curr = curr.next
    return curr

index(x):
	curr = __head #더미 헤드
    for index in range(__numItems):
    	curr = curr.next
        if curr.item == x:
        	return index
    return -12345 #x가 없을 때

isEmpty():            🧀 리스트가 비었는지 알려주기
	return __numItems == 0
size():               🧀 리스트의 총 원소 수 알려주기
	return __numItems
    
clear():              🧀 리스트 깨끗이 청소하기
	newNode.next = None    🧀 더미 헤드 노드
	__head = newNode
	__numItems = 0

 

10) 노드 객체를 만드는 클래스

class ListNode:
	def __init__(self, newItem, nextNode:'ListNode'):
    	self.item = newItem
        self.next = nextNode

a = ListNode(x, None)

👆 필드 item 값은 x, 필드 next 값은 None인 노드 객체를 만드는 코드

 

4. 연결 리스트의 구현

 1) 원소 삽입

#연결 리스트에 원소 삽입하기(더미 헤드 O 버전)
def insert(self, i:int, newItem):
	if i >= 0 and i <= self.__numItems:
    	prev = self.__getNode(i-1)
        newNode = ListNode(newItem, prev.next)
		prev.next = newNode
        self.__numItems += 1
    else:
    print("index", i, ": out of  bound in inser()") #필요 시 에러 처리

# 연결 리스트의 i번 노드 알려주기
def __getNode(self, i:int) -> ListNode:
	curr = self.__head #더미 헤드, index: -1
    for index in range(i+1):
    	curr = curr.next
    return curr

def append(self, newItem):
	prev = self.__getNode(self.__numItems - 1)
    newNode = ListNode(newItem, prev.next)
    prev.next = newNode
    self.__numItems += 1

 

2) 원소 삭제

def pop(self, i:int): #i번 노드 삭제, 고정 파라미터
	if (i >= 0 and i <= self.__numItems-1):
    	prev = self.__getNode(i-1)
        curr = prev.next
        prev.next = curr.next
        retItem = curr.item
        self.__numItems -= 1
        return retItem
    else:
    	return None

# 연결 리스트의 원소 x 삭제하기(더미 헤드 O 버전)
def remove(self, x):
	(prev, curr) = self.__findNode(x)
    if curr != None:
    	prev.next = curr.next
        self.__numItems -= 1
        
 def __findNode(self, x) -> (ListNdoe, ListNode):
 	prev = self.__head #더미 헤드
    curr = prev.next  #0번 노드
    while curr != None:
    	if curr.item == x:
        	return (prev, curr)
        else:
        	prev = curr; curr=curr.next
    return (None, None)

 

3) 기타 작업

# 연결 리스트의 i번 원소 알려주기
def get(self, i:int):
	if self.isEmpty():
    	return None
    if (i >=0 and i <=self.__numItems - 1):
    	return self.__getNode(i).item
    else:
    	return None

 

# x가 연결 리스트의 몇 번 원소인지 알려주기
def index(self, x)-> int:
	curr = self.__head.next
    for index in range(self.__numItems):
    	if curr.item == x:
        	return index
        else:
        	curr = curr.next
    return -12345 #안 쓰는 인덱스

def isEmpty(self) -> bool:
	return self.__numItems == 0
    
def size(self) -> int:
	return self.__numItems
    
def clear(self):
	self.__head = ListNode("dummy", None)
    self.__numItems = 0

def count(self, x) -> int:
	cnt = 0
    curr = self.__head.next #0번 노드
    while curr != None:
    	if curr.item == x:
        	cnt += 1
        curr = curr.next
    return cnt

def extned(self, a): #여기서 a는 self와 같은 타입의 리스트
	for index in range(a.size()):
    	self.append(a.get(index))

def copy(self):
	a = LinkedListBasic()
    for index in range(self.__numItem):
    	a.append(self.get(index))
    return a

def reverse(self):
	a = LinkedListBasic()
    for index in range(self.__numItems):
    	a.insert(0, self.get(index))
    self.clear()
    for index in range(a.size()):
    	self.append(a.get(index))

def sort(self) -> None:
	a = []
    for index in range(self.__numItems):
    	a.append(self.get(index))
    a.sort()
    self.clear()
    for index in range(len(a)):
    	self.append(a[index])

 

🥔 전체 코드

from DS.list.listNode import ListNode

class LinkedListBasic:
	def __init__(self):
    	self.__head = ListNode('dummy', None)
        self.__numItems = 0
        
#연결 리스트에 원소 삽입하기(더미 헤드 O 버전)
	def insert(self, i:int, newItem):
		if i >= 0 and i <= self.__numItems:
    		prev = self.__getNode(i-1)
        	newNode = ListNode(newItem, prev.next)
			prev.next = newNode
        	self.__numItems += 1
   	 	else:
    		print("index", i, ": out of  bound in inser()") #필요 시 에러 처리
    
    def append(self, newItem):
	prev = self.__getNode(self.__numItems - 1)
    newNode = ListNode(newItem, prev.next)
    prev.next = newNode
    self.__numItems += 1
    
    
    def pop(self, i:int): #i번 노드 삭제, 고정 파라미터
	if (i >= 0 and i <= self.__numItems-1):
    	prev = self.__getNode(i-1)
        curr = prev.next
        prev.next = curr.next
        retItem = curr.item
        self.__numItems -= 1
        return retItem
    else:
    	return None
        
# 연결 리스트의 원소 x 삭제하기(더미 헤드 O 버전)
	def remove(self, x):
		(prev, curr) = self.__findNode(x)
   	 	if curr != None:
			prev.next = curr.next
			self.__numItems -= 1
            return x
        else:
        return None
        
   # 연결 리스트의 i번 원소 알려주기
	def get(self, i:int):
		if self.isEmpty():
    		return None
   	 	if (i >=0 and i <=self.__numItems - 1):
    		return self.__getNode(i).item
    	else:
    		return None
        # x가 연결 리스트의 몇 번 원소인지 알려주기
	def index(self, x)-> int:
		curr = self.__head.next
    	for index in range(self.__numItems):
    		if curr.item == x:
        		return index
        	else:
        		curr = curr.next
    	return -12345 #안 쓰는 인덱스
        
    def isEmpty(self) -> bool:
		return self.__numItems == 0
    
    def size(self) -> int:
		return self.__numItems
    
	def clear(self):
		self.__head = ListNode("dummy", None)
        self.__numItems = 0
        
        
    self.__numItems = 0
    
    def count(self, x) -> int:
	cnt = 0
    curr = self.__head.next #0번 노드
    while curr != None:
    	if curr.item == x:
        	cnt += 1
        curr = curr.next
    return cnt
    
    def extned(self, a): #여기서 a는 self와 같은 타입의 리스트
		for index in range(a.size()):
    		self.append(a.get(index))
        
    def copy(self):
		a = LinkedListBasic()
    	for index in range(self.__numItem):
    		a.append(self.get(index))

    
    def reverse(self):
		a = LinkedListBasic()
    	for index in range(self.__numItems):
    		a.insert(0, self.get(index))
    	self.clear()
    	for index in range(a.size()):
    		self.append(a.get(index))
            
    def sort(self) -> None:
		a = []
    	for index in range(self.__numItems):
    		a.append(self.get(index))
    	a.sort()
    	self.clear()
    	for index in range(len(a)):
    		self.append(a[index])
            
	def __findNode(self, x) -> (ListNode, ListNode):
    	prev = self.__head #더미 헤드
        curr = prev.next #0번 노드
        while curr != None:
        	if curr.item == x:
            	return (prev, curr)
            else:
            	prev = curr; curr = curr.nest
        return (None, None)
        
# 연결 리스트의 i번 노드 알려주기
	def __getNode(self, i:int) -> ListNode:
		curr = self.__head #더미 헤드, index: -1
    	for index in range(i+1):
    		curr = curr.next
    	return curr  
        
        
def printList(self):
	curr = self.__head.next #0번 노드: 더미 헤드 다음 노드
    while curr != None:
    	print(curr.item, end=' ')
        curr = curr.next
    print()