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

찬은·2025년 3월 26일

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

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

목록 보기

3/10

3-1 리스트란?
3-2 배열 구조와 연결된 구조
3-3 배열 구조의 리스트: 파이썬 리스트
3-4 연결 리스트의 구조와 종류
3-5 단순 연결 구조로 리스트 구현하기
3-6 이중 연결 구조로 리스트 구현하기

03-1 리스트란?

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

리스트

자료들이 차례대로 나열된 선형 자료구조
각 자료는 순서 또는 위치를 가짐
리스트의 구조
- 리스트에서는 어떤 위치에서도 새로운 요소를 삽입 가능
- 어느 위치의 요소를 삽입, 삭제하면 모든 요소의 위치가 변경됨
집합(Set)과 차이
- 집합은 원소 사이에 순서가 없음
- 집합은 원소의 중복을 허용함
- 집합은 선형 자료구조가 아님

리스트의 연산

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

delete(pos): pos 위치에 있는 요소를 꺼내서 반환

getEntry(pos): pos위치에 있는 요소를 삭제하지 않고 반환

isEmpty(): 리스트가 비어있으면 True를, 아니면 False를 반환

isFull(): 리스트가 가득 차 있으면 True를, 아니면 False를 반환

size(): 리스트에 들어 있는 전체 요소의 수를 반환

Quiz

0 1 2 3
30 20 40 50
60
insert(size(), e)
집합은 순서가 없고 원소의 중복을 허용하며, 선형 자료구조가 아님

03-2 배열 구조와 연결된 구조

리스트의 모든 요소는 중간에 빈자리가 없어 반드시 메모리의 연속된 공간에 저장되어야 함

링크(link)

요소들이 다른 요소를 가리키는 하나 이상의 링크를 갖도록 하여 전체를 순서대로 연결해 관리하는 것

연결된 구조(linked structure)

메모리에 흩어져 있는 요소들을 링크로 연결해 하나로 관리하는 것

연결 리스트(linked list)

자료들을 링크를 통해 일렬로 나열할 수 있는 연결된 구조

노드(node)

연결된 구조에서 하나의 상자를 말하며, 데이터와 함께 링크를 가짐

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

리스트 요소들에 대한 접근

배열 구조는 모든 요소의 크기가 같고 연속된 메모리 공간에 있음
배열의 시작 주소와 요소 하나의 크기를 알고 있음

리스트의 용량

배열의 용량은 고정됨
- 배열을 크게 할당해 놓으면 메모리 낭비가 심함
- 배열을 적게 할당하면 포화 상태가 되어 새로운 요소를 넣지 못하는 상황 발생
연결된 구조는 용량이 고정되어 있지 않음
- 필요할 때 필요한 크기만큼 새로 할당해서 사용함
- 메모리를 효율적으로 사용 가능

리스트의 삽입 연산

배열 구조에서는 자료를 삽입하려면 그 위치 이후의 모든 요소를 한 칸씩 뒤로 밀어야 함
연결된 구조에서는 삽입할 위치를 알고 있다면 효율적인 삽입이 가능함

리스트의 삭제 연산

배열 구조에서는 자료를 삭제하면 이후의 모든 자료를 앞으로 당겨야 함
연결된 구조에서는 삭제할 노드 바로 앞 노드의 링크만 수정하면 되고, 다른 노드는 수정할 필요가 없음

Quiz

2400
99번째 요소의 링크를 알아내면 됨

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

파이썬의 리스트 멤버함수

파이썬 리스트는 용량이 제한되지 않도록 구현됨

용량을 늘리는 방법
- 1단계: 기존의 리스트보다 용량을 늘린(예를 들어, 2배) 새로운 리스트를 할당함
- 2단계: 기존의 리스트의 모든 요소를 새로운 리스트에 모두 복사함, 새로운 리스트는 기존 리스트와 같은 요소들을 갖지만, 여유 공간이 많이 남아있음
- 3단계: 새로운 리스트에 새로운 요소 I 삽입, 여유 공간이 확보되었기 때문에 가능
- 4단계: 기존 리스트 대신에 새로운 리스트 사용

Quiz

4번

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

연결 리스트의 구조

노드(node)

연결 리스트에서 하나의 노드(node)는 하나의 데이터(data)와 함께 하나 이상의 링크(link)를 가짐
링크(link)는 다른 노드를 다리키는(다른 노드의 주소를 저장하는) 변수

헤드 포인터(head pointer)

머리 노드(head node): 링크로 매달려 있는 모든 노드에 순차적으로 접근 가능한 노드
헤드 포인터(head pointer): 머리 노드의 주소를 저장하는 변수
꼬리 노드(tail node): 꼬리 노드의 링크를 처리하는 방법에 따라 단순 연결과 원형 연결로 구분됨

연결 리스트의 종류

단순 연결 리스트(singly linked list)

하나의 방향으로만 연결된 리스트
꼬리 노드의 링크는 마지막 노드라는 것을 나타내기 위해 None을 가짐

원형 연결 리스트(circular linked list)

꼬리 노드의 링크를 None이 아니라 다시 머리 노드를 가리킴
노드들을 순서대로 방문할 때 종료 조건 처리에 조심

이중 연결 리스트(doubly linked list)

두 개의 링크를 가지는데 하나는 이전 노드(previous node)를 다른 하나는 다음 노드(next node)를 가리킴
장) 어떤 노드에서도 이전 노드를 찾아갈 수 있음
단) 코드가 복잡함

Quiz

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

단순 연결 구조 노드 클래스 구현

Node 클래스의 정의와 생성자

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

새로운 노드를 뒤에 추가하는 append() 연산

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

다음 노드를 연결 구조에서 꺼내는 Node 클래스의 popNext() 연산

	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

단순 연결 리스트 클래스의 연산

공백 상태와 포화 상태를 검사하는 isEmpty() 와 isFull() 연산

연결된 구조에서는 메모리만 남아있다면 언제든지 노드를 추가할 수 있음

	def isEmpty(self):
    	return self.head == None
    def isFull(self):
    	return False

pos번째 노드를 반환하는 getNode(pos) 연산

	def getNode(self, pos):
		if pos < 0 : return None
		ptr = self.head
		for i in range(pos):
			if ptr == None :
				return None
			ptr=ptr.link
		return ptr

pos번째 요소를 반환하는 getEntry(pos) 연산

def getEntry(self, pos)
	node = self.getNode(pos) 
	if node == None : return None 
	else: return node.data

pos 위치에 새로운 요소를 삽입하는 insert(pos, e) 연산

pos 위치에 새로운 노드를 삽입하려면 pos-1 위치의 노드 before을 알아야 함

def insert(self, pos , e):
	node = Node(e , None)
	before = self.getNode(pos-1)
	if before == None:
    	node.link = self.head
        self.head = node
    else: before.append(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()

전체 요소의 수를 구하는 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’)

연결 리스트와 파이썬 리스트 비교

구현 방법이 다르더라도 동작은 일치함

Quiz

def replace(self, pos, e):
        ptr = self.head
        index = 0
        
        # pos 번째 노드 찾기
        while node:
            if index == pos:
                ptr.data = e  # 값 변경
                return True
            ptr = ptr.next
            index += 1

class LinkedList:
	def __init__(self):
    	self.head = None
        self.count = 0
        
    def insert(self, pos , e):
        node = Node(e , None)
        before = self.getNode(pos-1)
        if before == None:
            node.link = self.head
            self.head = node
        else : before.append(node) 
        self.count += 1

단순히 값만을 반환하게 되어 효율적이게 됨

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

이중 연결 구조를 위한 노드 클래스

이중 연결 구조의 노드 클래스 정의와 생성자

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

새로운 노드를 뒤에 추가하는 DNote 클래스의 append() 연산

	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

다음 노드를 연결 구조에서 꺼내는 DNote 클래스의 popNext() 연산

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

이중 연결 리스트 클래스

이중 연결 리스트 클래스 정의와 연산자

class DblLinkedList:
	def __init__(self):
    	self.head = None

isEmpty(), isFull, getEntry(pos)

isEmpty(), isFull(), getEntry()은 LinkedList 클래스에서 코드와 정확히 동일
LinkedList의 getNode(), size(), display() 등의 연산에서 .link를 .next로 수정하면 이중 연결 리스트에서도 동작

	def display(self, msg=’DblLinkedList: ’):
		print(msg, end=' ')
		ptr = self.head
		while ptr is not None:
			print(ptr.data, end= ’<=>’)
			ptr = ptr.next
		print('None ')

pos 위치에 새로운 요소를 삽입하는 insert(pos, e) 연산

    def insert(self, pos, e):
        node = DNode(e) 
        before = self.getNode(pos-1) 
        if before == None:
            node.next = self.head
            if node.next is not None:
                node.next.prev = node
            self.head = node
        else: before.append(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.next
    		if self.head is not None: 
    			self.head.prev = None
    		return before
    	else: before.popNext()

이중 연결 리스트 클래스 테스트

아래 코드에서 1행 s = DblLinkedList() 만 수정하면 동일

Quiz

isEmpty(), isFull(), getEntry()

연습문제

01

delete(pos) list.pop(pos)
getEntry(pos) list[pos]
isEmpty() len(lst) == 0
size() len(lst)

02

def find(self, e):
    cur = self.head
    index = 0
    while cur:
        if cur.data == e:
            return index
        cur = cur.next
        index += 1
    return -1  # 없을 경우

03

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

class Stack:
    def __init__(self):
        self.top = None
    
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
    
    def pop(self):
        if self.is_empty():
            return None
        data = self.top.data
        self.top = self.top.next
        return data
    
    def peek(self):
        return None if self.is_empty() else self.top.data
    
    def is_empty(self):
        return self.top is None

    def display(self):
        cur = self.top
        while cur:
            print(cur.data, end=" -> ")
            cur = cur.next
        print("None")

04

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

class Queue:
    def __init__(self):
        self.front = self.rear = None
    
    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:  # 처음 추가하는 경우
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
    
    def dequeue(self):
        if self.is_empty():
            return None
        data = self.front.data
        self.front = self.front.next
        if self.front is None:  # 마지막 노드였을 경우
            self.rear = None
        return data
    
    def is_empty(self):
        return self.front is None
    
    def display(self):
        cur = self.front
        while cur:
            print(cur.data, end=" -> ")
            cur = cur.next
        print("None")

05

단순 연결 리스트에서는 후단 삭제(Rear Deletion) 를 하려면 마지막 노드를 삭제해야 함
하지만 이전 노드(prev) 참조 없이 마지막 노드를 찾을 수 없음
따라서 head부터 시작해 마지막 이전 노드까지 순회해야 함

06

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

class DoublyCircularLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
            self.head.prev = self.head
        else:
            last = self.head.prev
            last.next = new_node
            new_node.prev = last
            new_node.next = self.head
            self.head.prev = new_node

    def delete(self, data):
        if not self.head:
            return
        
        cur = self.head
        while True:
            if cur.data == data:
                if cur == self.head and cur.next == self.head:  # 마지막 노드 삭제
                    self.head = None
                    return
                
                cur.prev.next = cur.next
                cur.next.prev = cur.prev
                
                if cur == self.head:  # head 삭제 시
                    self.head = cur.next
                
                return
            
            cur = cur.next
            if cur == self.head:
                break

    def display(self):
        if not self.head:
            print("List is empty")
            return
        
        cur = self.head
        while True:
            print(cur.data, end=" <-> ")
            cur = cur.next
            if cur == self.head:
                break
        print("(Back to Head)")

찬은

이전 포스트

[자료구조와 알고리즘 with 파이썬] 02 큐

다음 포스트

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

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

03-1 리스트란?

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

리스트

리스트의 연산

Quiz

03-2 배열 구조와 연결된 구조

링크(link)

연결된 구조(linked structure)

연결 리스트(linked list)

노드(node)

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

리스트 요소들에 대한 접근

리스트의 용량

리스트의 삽입 연산

리스트의 삭제 연산

Quiz

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

파이썬의 리스트 멤버함수

파이썬 리스트는 용량이 제한되지 않도록 구현됨

Quiz

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

연결 리스트의 구조

노드(node)

헤드 포인터(head pointer)

연결 리스트의 종류

단순 연결 리스트(singly linked list)

원형 연결 리스트(circular linked list)

이중 연결 리스트(doubly linked list)

Quiz

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

단순 연결 구조 노드 클래스 구현

Node 클래스의 정의와 생성자

새로운 노드를 뒤에 추가하는 append() 연산

다음 노드를 연결 구조에서 꺼내는 Node 클래스의 popNext() 연산

단순 연결 리스트 클래스의 데이터

단순 연결 리스트 클래스의 연산

공백 상태와 포화 상태를 검사하는 isEmpty() 와 isFull() 연산

pos번째 노드를 반환하는 getNode(pos) 연산

pos번째 요소를 반환하는 getEntry(pos) 연산

pos 위치에 새로운 요소를 삽입하는 insert(pos, e) 연산

pos 위치의 요소를 삭제하는 delete(pos) 연산

전체 요소의 수를 구하는 size() 연산

리스트를 보기 좋게 화면에 출력하는 display() 연산

연결 리스트와 파이썬 리스트 비교

Quiz

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

이중 연결 구조를 위한 노드 클래스

이중 연결 구조의 노드 클래스 정의와 생성자

새로운 노드를 뒤에 추가하는 DNote 클래스의 append() 연산

다음 노드를 연결 구조에서 꺼내는 DNote 클래스의 popNext() 연산

이중 연결 리스트 클래스

이중 연결 리스트 클래스 정의와 연산자

isEmpty(), isFull, getEntry(pos)

pos 위치에 새로운 요소를 삽입하는 insert(pos, e) 연산

pos 위치의 요소를 삭제하는 delete(pos) 연산

이중 연결 리스트 클래스 테스트

Quiz

연습문제

01

02

03

04

05

06

[자료구조와 알고리즘 with 파이썬] 02 큐

[자료구조와 알고리즘 with 파이썬] 04 트리

0개의 댓글