[자료구조와알고리즘with파이썬] Ch.03 리스트

리스트란?

: 선형 자료구조로 어느 위치에서든 새로운 요소를 삽입하고 삭제할 수 있다.

- 배열 구조의 리스트와 연결 리스트가 있다.

---

배열구조의 리스트		연결 리스트
		노드, 링크
모든 요소의 크기가 같고 연속된 메모리 공간에 있기 때문에 n번째 요소의 위치는 " 시작주소 + 요소의 크기 * k "	요소 접근	k번째 요소를 찾기 위해서는 첫 번째 요소부터 k-1번 링크를 따라 이동해야함
너무 많이 할당하면 낭비하는 메모리가 생길 수도 있기 때문에 고정된 용량을 가짐	리스트 용량	무제한 생성될 수 있음
그 위치 이후에 있는 모든 요소들의 위치를 옮겨야 함	삽입 / 삭제	중간에 넣고 이전 노드의 링크와 자신의 링크를 수정하면 됨

 

---

배열구조의 리스트

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

---

연결 리스트

https://velog.io/@tataki26/%EB%A7%81%ED%81%AC%EB%93%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결리스트는 노드를 가진다. 

하나의 노드에는 데이터(요소)와 링크가 있다. 

링크에는 다음 노드의 주소에 대한 정보가 담겨있다.

---

마지막 노드 (즉 꼬리노드)의 링크를 처리하는 방법에 따라 단순 연결과 원형 연결로 구분된다.

* 머리 노드의 주소 저장 변수 : head pointer

* 머리 노드 : head node

* 꼬리 노드 : tail node

 

[단순 연결 리스트]

: 꼬리 노드의 링크는 꼬리 노드가 마지막이라는 것을 나타내기 위해 None을 가짐

 

[원형 연결 리스트]

: 꼬리 노드의 링크가 다시 머리 노드를 가리키는 구조

 

[이중 연결 리스트]

: 하나의 노드가 이전 노드와 다음 노드의 링크를 모두 갖는 구조

---

[단순 연결 리스트 구현] : 노드 클래스

class Node:
	def _init_ (self, elem, link = None):
    	self.data = elem #데이터 멤버 생성 및 초기화
        self.link = link #링크 생성 및 초기화

 

 

def append(self, node): #self다음에 node를 넣음
	if node is not None:
    	node.link = self.link
        self.link = node

: self노드 뒤에 self.link노드가 있는데 이 사이에 node 노드를 추가하려는 경우
1) node노드의 링크 node.link가 다음 노드인 self.link노드를 가리키게 함 -> node.link = self.link 
2) self노드의 링크는 node노드를 가리키게 함 -> self.link = node
현재 노드의 링크 = 다음 노드 

 

 

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

 

 

class LinkedList: #단순 연결 리스트 클래스 생성
	def _init_(self): #생성자
    	self.head = None # head선언 및 None으로 초기화

 

 

[ pos번째 노드를 반환: getNode(pos) ]

def getNode(self, pos):
	if pos<0: return None #잘못된 위치에서 시작한다면 None반환시킴
    ptr = self.head #시작은 head에서부터
    for i in range(pos):
    	if ptr == None:
        	return None
        ptr = ptr.link
        #pos위치의 노드에 도착해서 ptr에 해당 노드의 링크를 넣음
    return ptr #최종 노드 반환

최대한 비슷한 사진

 

[ pos번째 요소를 반환: getNode(pos) ]

def getEntry(self, pos):
	node = self.getNode(pos) #pos번째 노드를 구함
    if node == None: return None #해당 노드가 없는 경우 None을 반환
    else: return node.data #있는 경우 데이퍼 반환

 

 

[ pos위치에 새로운 요소를 삽입: insert(pos, e) ]

pos위치에 새로운 노드를 삽입하기 위해서는 그 전 노드에 대해서 알고 있어야 한다. 그 전 노드의 링크가 새로 삽입시킬 노드를 가리키도록 바꿔야 하기 때문이다.

def insert(self,pos,e): #self라는 리스트, pos라는 삽입위치, e라는 삽입할 요소
	node = Node(e, None) #삽입할 새로운 node노드
    before = self.getNode(pos-1)
    if before == None:
    	node.link = self.head
        self.head = node
    else: before.append(node) #before노드 뒤에 node노드를 추가함

 if before == None;인 경우는 새롭게 삽입하려는 node노드의 위치가 리스트의 맨 앞이라는 것을 뜻한다. 따라서 node노드를 head노드로 바꿔주기 위해서 node노드의 링크는 self.head를, 시작노드는 node노드를 가리키도록 설정한다. 

 

 

[ pos위치의 요소를 삭제: delete(pos) ]

def delete(self,pos):
	before = self.getNode(pos-1) #삭제할 위치 이전 노드 탐색
    if before == None:
    	before = self.head
        if self.head is not None:
        	self.head = self.head.link
        return before
    else: return before.popNext() #before의 다음 노드 삭제

삭제도 삽입과 마찬가지로 삭제하려는 노드의 앞에 있는 노드 위치를 알아야 한다. (pos-1)
before노드가 머리노드인 경우에는 ........................

 

[ 전체 요소의 수 구하기: size( ) ]

def size(self):
	ptr = self.head
    count = 0;
    while ptr is not None:
    	ptr = ptr.link #링크를 따라 포인터가 이동함
        count += 1
    return count

 

 

[ 리스트를 보기 좋게 화면에 출력하기: display( ) ]

: 모든 노드를 순서대로 방문해야 한다.

def display(self, msg = 'LinkedList: '):
	print(msg, end=' ')
    ptr = self.head
    while ptr is not None:
    	print(ptr.data, end='->')
        ptr = ptr.link
    print('None')

ptr = ptr.link를 사용해서 노드의 요소 출력 후에는 다음 노드로 갈 수 있도록 포인터를 바꿔준다.