자료구조와 알고리즘 with 파이썬 chapter3

3-1. 리스트란?

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

리스트에서는 어떤 위치에서도 새로운 요소를 삽입할 수 있다.

집합	리스트
원소 사이에 순서가 없다.	순사가 있다.
원소의 중복을 허용하지 않는다.	중복 허용
선형 자료구조가 아니다	선형 자료구조

리스트의 연산

• insert(pos, e) : pos 위치에 새로운 요소 e를 삽입
• delete(pos) : pos 위치에 있는 요소를 꺼내서 반환
• getEntry(pos) : pos 위치에 있는 요소를 삭제하지 않고 반환
• isEmpty( ) : 리스트가 비어 있으면 True를, 아니면 False를 반환
• isFull( ) : 리스트가 가득 차 있으면 True를, 아니면 False를 반환
• size( ) : 리스트에 들어 있는 전체 요소의 수를 반환
• replace(pos, e) : pos번째 요소를 변경
• display( ) : 리스트를 화면에 보기 좋게 출력

3-2. 배열 구조와 연결된 구조

리스트도 배열구조와 연결된 구조로 구현.

배열 구조의 리스트와 연결 리스트의 비교

1) 리스트 요소들에 대한 접근

배열 구조는 모든 요소의 크기가 같고 연속된 메모리 공간에 있다. 또한, 배열의 시작 주소와 요소 하나의 크기를 알고 있다. k번째 요소의 위치는 한 요소의 크기에 원하는 위치를 곱해 시작 주소에 더해준다. 

연결된 구조는 k번째 요소를 찾으려면 어쩔 수 없이 시작노드에서부터 k-1번 링크를 따라 이동해야 한다.

2) 리스트의 용량

기본적으로 배열은 용량이 고정.

연결된 구조는 용량이 고정되어 있지 않다. 필요할 때 필요한 크기만큼 새로 할당해서 사용.

3-3. 배열구조의 리스트:파이썬리스트

 

append(e)	새로운 요소 e를 추가
extend(lst)	리스트 lst를 리스트 s에 삽입
count(e)	리스트에서 요소 e의 개수를 세어 반환
index(e,[시작],[종료])	요소 e가 나타나는 가장 작은 위치(인덱스)를 반환합니다. 탐색을 위한 시작 위치와 종료 위치를 지정할 수 도 있다.
insert(pos, e)	pos 위치에 새로운 요소 e를 삽입한다.
pop(pos)	pos 위치의 요소를 꺼내고 반환
pop( )	맨 뒤의 요소를 거내고 반환
remove(e)	요소 e를 리스트에서 제거
reverse( )	리스트 요소들의 순서를 뒤집는다.
sort([key],[reverse])	요소들을 key를 기준으로 오름차순으로 정렬. reverse=True이면 내림차순으로 정렬.

3 - 4. 연결 리스트의 구조와 종류

노드

노드는 하나의 데이터와 함께 하나 이상의 링크를 갖는다. 

링크는 다른 노드를 가리키는(다른 노드의 주소를 저장하는)변수

헤드 포인터

- 연결 리스트는 시작  노드만 알면 링크로 매달려 있는 모든 노드에 순차적으로 접근가능. 이 시작노드를 머리 노드라고 한다.

- 머리 노드의 주소를 저장하는 변수를 헤드 포인터라고 한다.- 마지막 노드를 보통 꼬리 노드 라고 한다.

연결 리스트 종류

• 단순 연결 리스트 : 하나의 방향으로만 연결된 리스트. 꼬리 노드의 링크는 마지막 노드라는 것을 나타내기 위해 None을 갖기로 약속 되어 있다.
• 원형 연결 리스트 : 꼬리 노드의 링크가 None이 아니라 다시 머리 노드를 가리키도록 하는 것. 어떤 노드에서 시작해도 다른 모든 노드를 찾아갈 수 있다. 
• 이중 연결 리스트 : 하나의 노드가 이전 노드와 다음 노드의 링크를 모두 갖도록 설계. 두 개의 링크를 갖는데, 하나는 이전 노드를, 다른 하나는 다음 노드를 가리키도록 하는 것. 

3-5. 단순 연결 구조로 리스트 구현하기

 

class Node:
	def __init__ (self, elem, link=None):
    	self.data = elem
        self.link = link

 

def append(self, node):
	if node is not None:
    	node.link = self.link
        self.link = None

def popNext(self):
	next = self.link
    if next is not None:
    	self.link = next.link
    return next

3-6 이중 연결 구조로 리스트 구현하기

 

class DNode:
	def __init__ (self, elem, prev=None, next=None):
    	self.data= elem
        self.next = next
        self.prev = prev

def append(self, node):
	if node is not None:
    	node.next = self.next
        node.prev = self
        if node.next is not None:
        	node.next.prev = node
        self.next = node

def popNext(self):
	node = self.next
    if node is not None:
    	self.next = node.next
        if self.next is not None:
        	self.next.prev = self
        return node