자료구조2 - 배열과 연결리스트

자료구조란, 추상적 자료형의 구체적 표현이라고 하였다.

이번 자료구조2에서는 리스트라는 추상적 자료형의 자료구조에 대해 공부해보도록 하겠다.

리스트는 평소에 파이썬을 쓸 때 자주 썼었는데 여기서 말하는 추상적 자료형인 리스트는 그 리스트가 아니다.

오히려 리스트라는 추상적 자료형을 구현한 대표적인 예시가 우리가 알던 리스트 즉, 배열이다.

이와 같이 리스트를 구현한 자료구조 중 대표적인 다른 예시는 연결리스트이다.

 

<연결리스트의 정의와 방식>

연결 리스트란, 각 자료를 여러 개의 노드에 저장하는 방식으로 구현한다.

여기서 노드는 => 자료 + 포인터를 가진다.

노드의 포인터는 다음 노드를 가리키고, 이러한 노드들이 연결되어 연결 리스트가 되는 것이다.

 

이러한 연결리스트에서 특정한 자료를 찾을 때는 어떻게 해야될까?

어쩔 수 없이 처음 시작노드부터 차례대로 조회하여야 한다.==> 단점

배열은 찾는 자료의 위치와 관계없이 한 번에 바로 값을 찾을 수 있지만, 연결리스트는 찾고자하는 자료의 위치가 시작점부터 멀수록 연산 횟수가 많아지는 큰 단점을 갖고있다.

그렇다면, 배열을 냅두고 연결리스트를 구현하는 이유는 무엇일까?

연결 리스트는 자료의 추가&삭제에서 큰 장점을 지니고 있다.

조회 연산과 마찬가지로 삽입/삭제할 위치를 찾아야하는 과정은 조회와 동일하다.

하지만, 노드를 이용한 추가&삭제는 매우 용이하다.

 

연결리스트의 삽입 원리

연결리스트의 삭제 원리

 

배열의 삽입&삭제는 어떨까?

삽입/삭제할 자료를 찾는건 쉽다. 하지만, 삽입/삭제를 한 뒤에 해당 자료의 앞 자료들 or 뒷 자료들을 모두 한칸씩 뒤/앞으로 이동시켜야하므로 많은 연산이 이루어진다는 단점이 있다.

위의 사진을 보면 알 수 있듯이 연결리스트의 삽입&삭제는 배열에 비해 간편하다는 것을 알 수 있다.

 

 

이처럼, 리스트라는 추상적 자료형을 배열, 리스트, 연결리스트 등,, 여러 가지 형태로 구현할 수 있는데

각각 장단점이 존재하므로 여러 상황에 맞추어 그때 그때 더 효울적인 자료형을 쓰기 위하여 자료구조를 학습하는 것이다.

 

<연결리스트의 구현>

파이썬 기본 라이브러리 중, '큐'라는 자료구조를 구현한 Queue클래스도 있다.

큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있어 import하여 사용하면 된다.

연결 리스트는 구현이 비교적 간단하여 보통 구현하여 많이 사용한다.

 

그럼 연결리스트를 구현해보자

연결리스트를 구현하기 위해서는 2가지 클래스가  필요하다.

1. 연결리스트를 구성할 노드 클래스

2. 노드 클래스를 이용하여 만드는 연결리스트 클래스

 

노드 구현

# 1. 연결리스트를 구성할 노드 클래스
class Node:
	def__init__(self, data):
    	self.data=data
        self.next=None

위 코드는 노드 클래스를 작성한 것으로, 생성자를 통하여 자동으로 노드를 초기화 시켜준다.

노드의 데이터로 데이터가 들어가고, 다음 노드를 가리키는 포인터로는 아무런 값도 주지 않는다.

 

 

단일 연결 리스트 구현

 

# 노드 클래스
class Node:
    def __init__(self, data):   # 초기화
        self.data = data
        self.next = None

# 연결 리스트 클래스
class LinkedList:
    def __init__(self, data):   # 초기화
        self.head = Node(data)    # 첫 번째 노드 지정

    def add(self, data):    #노드 추가 함수
        if self.head is None:    #첫 번째 노드가 없을 때
            self.head = Node(data)    # 연결 리스트의 헤드 노드가 추가한 노드가 됨
        else:
            node = self.head      # 연결 리스트의 시작 노드를 변수에 저장(순회하기 위해)
            while node.next:     # 현재 노드의 다음 노드가 있다면
                node = node.next      #노드를 계속 이동시키면서 마지막 노드를 찾으려고 순회
            node.next = Node(data)  #마지막 노드에 새로운 노드를 추가

    def describe(self):     # 연결 리스트 순회 출력
        node = self.head    # 연결 리스트의 헤드 노드를 변수에 저장
        while node:
            print(node.data)
            node = node.next      # 노드를 이동시키면서 마지막 노드를 찾으려고 순회

    def delete(self, data):     # 노드 삭제 함수
        if self.head is None:
            print("삭제할 노드가 없습니다.")
        else:
            if self.head.data == data:      # 삭제할 노드가 첫 번째 노드일 때
                temp = self. head
                self.head = self.head.next    # 새로운 헤드 노드를 원래 헤드노드의 다음 노드로 지정
                del temp

            node = self. head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                node = node.next    # 다음 노드로 이동

            if node.data == data:   # 삭제할 데이터가 마지막 노드일 경우
                del node


    def search(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            node = node.next
        print("찾으시는 노드가 없습니다.")

 

이중 연결 리스트 구현

 

 

 

 

기존 단일 연결리스트에서 이전 노드를 가리키는 포인터가 추가된 형태

 

# 이중연결리스트의 구현

class Node:  # 노드 구현
    def __init__(self, data, prev=None, next=None):  # 반드시 초기화 할 것
        self.data = data
        self.prev = prev
        self.next = next


class DList:  # 이중 연결 리스트 구현
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail  # 헤드, 테일 노드 연결
        self.size = 0  # 사이즈 0

    def listSize(self):  # 연결 리스트의 사이즈
        return self.size

    def empty(self):  # 연결 리스트가 비었는지 여부 확인
        if self.size == 0:
            return 1
        else:
            return 0

    def selectNode(self, index):  # 특정 인덱스의 노드 찾기
        if index > self.size:
            print("Overflow:Index Error")
            return None
        elif index == 0:
            return self.head
        elif index == self.size:
            return self.tail

        current = self.head
        for i in range(index):
            current = current.next
        return current

    def appendleft(self, n):  # 왼쪽에 노드 추가
        if self.empty() == 1:
            self.head = Node(n)
            self.tail = Node(None, self.head)
            self.head.next = self.tail
        else:
            tmp = self.head
            self.head = Node(n, None, self.head)
            tmp.prev = self.head
        self.size += 1

    def append(self, n):    # 끝에 노드 추가
        if self.empty() == 1:
            self.head = Node(n)
            self.tail = Node(None, self.head)
            self.head.next = self.tail
        else:
            new = Node(n, self.tail.prev, self.tail)
            self.tail.prev.next = new
            self.tail.prev = new
        self.size += 1

    def insert(self, n, index):     # 특정 인덱스에 노드 삽입
        if self.empty() == 1:
            self.head = Node(n, None, self.tail)
            self.tail = Node(None, self.head, None)
        else:
            tmp = self.selectNode(index)  # 해당 인덱스를 가진 노드를 변수에 저장
            if tmp == None:
                return
            elif tmp == self.head:
                self.appendleft(n)  # 그냥 앞에다가 노드를 추가해주면 됨
            elif tmp == self.tail:
                self.append(n)  # 그냥 뒤에다가 노드를 추가해주면 됨
            else:
                new = Node(n, tmp.prev, tmp)
                tmp.prev.next = new
                tmp.prev = new
        self.size += 1

    def delete(self, index):    # 특정 노드 삭제
        if self.empty() == 1:
            print("Underflow Error")
            return
        else:
            tmp = self.selectNode(index)
            if tmp == None:
                print("삭제할 노드가 없습니다.")
                return
            elif tmp == self.head:
                tmp2 = self.head
                self.head = self.head.next
            elif tmp == self.tail:
                tmp2 = self.tail
                self.tail = self.tail.prev
            else:
                tmp2 = tmp
                tmp.prev.next = tmp.next
                tmp.next.pre = tmp.prev
            del tmp2    # 노드 삭제
            self.size -= 1

    def printlist(self):     #모든 데이터 출력
        current = self.head
        while current.next: # current가 아님 주의! tail은 None 값이 들어가 있을수도 있으므로 그 전 노드의 다음 노드가 있는지 없는지 확인 필요
            print(current.data, end=" ")
            current = current.next  # 옆으로 이동하면서 조회
        print()