선형 자료구조 - 연결리스트

• 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장
• 첫 노드를 head 끝 노드를 tail이라 한다.
• 단일 / 이중 / 원형 연결리스트가 있다.
  
  

1. 단일 연결 리스트

• 하나의 노드가 하나의 데이터와 하나의 포인터를 가지고 있다.
• 포인터는 다음 노드를 가리킨다.
  
  

단일 연결 리스트 구현

우선 노드의 구조를 만들어야 한다. 각 노드는 데이터를 가지고 있고, 단일 연결이기 때문에 하나의 next값을 가지고 있다.

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

다음으로 연결 리스트 class를 정의해준다.

class linkedList():
    def __init__(self, data = None):
        new_node = Node(data)
        self.head = new_node
        self.tail = new_node
        self.size = 1

data 값에 기본값을 None으로 해서 그냥 리스트만 만드는 경우도 생각해줬다. 다른 데이터를 넣을 경우 해당 데이터를 가진 노드가 만들어진다. 또한 맨 끝에 삽입하는 경우 빠르게 동작하게 하기 위해서 head와 더불어 tail도 만들었다.


단일 연결리스트의 메서드로 맨 앞 삽입, 맨 뒤 삽입, 중간 삽입, 삭제, 크기 반환, 출력 이렇게 6가지를 구현했다.

    def insertHead(self, data):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size += 1
        else:
            new_node = Node(data)
            tmp = self.head
            self.head = new_node
            self.head.next = tmp
            self.size += 1

    def insertTail(self, data):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size += 1
        else:
            new_node = Node(data)
            self.tail.next = new_node
            self.tail = new_node
            self.size += 1

먼저 맨 앞에 노드를 삽입하는 경우, 새 노드의 next가 될 현재 head를 가리키는 tmp를 만든다. 그 다음 head를 새 노드로 바꾼 뒤 next를 지정해준다.

맨 뒤에 삽입하는 경우는 tmp를 만들 필요가 없다.

    def insertMiddle(self, data, index):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size = 1
        elif index > self.size:
            self.insertTail(data)
        else:
            new_node = Node(data)
            tmp = self.selectNode(index)
            new_node.next = tmp.next
            tmp.next = new_node
            self.size += 1

    def selectNode(self, index):
        if index > self.size:
            return 'overflow'
        else:
            target = self.head
            count = 1
            while count < index:
                target = target.next
                count += 1
            return target

중간에 노드를 삽입하려면 먼저 해당 노드의 위치를 찾아야 한다. index를 이용해서 노드위 위치를 찾는데 내가 구현한 연결리스트의 index는 1부터 시작한다


중간이란 index와 해당 index 뒤에 노드 사이를 말한다. 예를 들어 index가 2일 경우 2와 3 사이가 된다.

삭제는 맨 앞 노드, 맨 뒤 노드, 중간 노드 세 부분으로 나뉘어 있고, 범위를 넘어서는 경우 삭제가 일어나지 않는다.

    def deleteNode(self, index):
        if index < 1:
            return 'underflow'
        elif index > self.size:
            return 'overflow'

        if index == 1: # 맨 앞 노드 삭제
            tmp = self.selectNode(1)
            self.head = self.head.next
            del tmp
        elif index == self.size: # 맨 뒤 노드 삭제
            tmp = self.selectNode(self.size - 1)
            self.tail = tmp
            del self.tail.next
            self.tail.next = None
        else: # 중간의 노드 삭제
            tmp = self.selectNode(index - 1)
            tmp.next = tmp.next.next
            # del_node = tmp.next
            # del del_node
        self.size -= 1

마지막으로 출력과 크기 반환 메서드

    def __str__(self):
        tmp = self.head
        result = '['
        for i in range(1, self.size + 1):
            result += str(tmp.data) + ', '
            tmp = tmp.next
        result = result[:-2] + ']'
        return result
        
    def sizePrt(self):
        print(self.size)
        return

2. 이중 연결 리스트

• 단일 연결 리스트의 next에 추가로 이전 노드를 가리키는 것까지 포함하는 연결리스트
• 양방향 연결이 필요하다.

이중 연결리스트 구현

양 끝단 삽입의 경우 이전 노드를 가리키는 prev를 지정하는 부분을 추가하면 된다. 또한 삭제를 할 때 노드 위치를 저장할 tmp가 필요해진다.

    def insertHead(self, data):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size += 1
        else:
            new_node = Node(data)
            tmp = self.head
            self.head = new_node
            self.head.next = tmp
            tmp.prev = self.head
            self.size += 1

    def insertTail(self, data):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size += 1
        else:
            new_node = Node(data)
            tmp = self.tail
            self.tail.next = new_node
            self.tail = new_node
            self.tail.prev = tmp
            self.size += 1
            
    def insertMiddle(self, data, index):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size = 1
        elif index > self.size:
            self.insertTail(data)
        else:
            new_node = Node(data)
            tmp = self.selectNode(index)
            new_node.prev = tmp
            new_node.next = tmp.next
            tmp.next.prev = new_node
            tmp.next = new_node
            self.size += 1

삭제를 할 때도 노드를 삭제 하기 전에 prev를 지정해 주는 것만 빼면 동일하다

    def deleteNode(self, index):
        if index < 1:
            return 'underflow'
        elif index > self.size:
            return 'overflow'

        if index == 1: # 맨 앞 노드 삭제
            tmp = self.selectNode(1)
            self.head = self.head.next
            del tmp
        elif index == self.size: # 맨 뒤 노드 삭제
            tmp = self.selectNode(self.size - 1)
            self.tail = tmp
            del self.tail.next
            self.tail.next = None
        else: # 중간의 노드 삭제
            tmp = self.selectNode(index - 1)
            tmp.next = tmp.next.next
            tmp.next.next.prev = tmp
            del_node = tmp.next
            del del_node
        self.size -= 1

3. 원형 연결 리스트

• 이중 연결리스트에서 head와 tail이 연결되어 있는 형태이다.
• 이중 연결 리스트에서 양 끝 단의 삭제 연산과 삽입 연산에서 수정이 필요하다.

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

class linkedList():
    def __init__(self, data = None):
        new_node = Node(data)
        self.head = new_node
        self.tail = new_node
        if data == None:
            self.size = 0
        else:
            self.size = 1

    def __str__(self):
        tmp = self.head
        result = '['
        for i in range(1, self.size + 1):
            result += str(tmp.data) + ', '
            tmp = tmp.next
        result = result[:-2] + ']'
        return result

    def insertHead(self, data):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size += 1
        else:
            new_node = Node(data)
            tmp = self.head
            self.head = new_node
            self.head.next = tmp
            tmp.prev = self.head
            self.head.prev = self.tail
            self.tail.next = self.head
            self.size += 1

    def insertTail(self, data):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size += 1
        else:
            new_node = Node(data)
            tmp = self.tail
            self.tail.next = new_node
            self.tail = new_node
            self.tail.prev = tmp
            self.tail.next = self.head
            self.head.prev = self.tail
            self.size += 1

    def insertMiddle(self, data, index):
        if self.head.data == None:
            new_node = Node(data)
            self.head = new_node
            self.tail = new_node
            self.size = 1
        elif index > self.size:
            self.insertTail(data)
        else:
            new_node = Node(data)
            tmp = self.selectNode(index)
            new_node.prev = tmp
            new_node.next = tmp.next
            tmp.next.prev = new_node
            tmp.next = new_node
            self.size += 1

    def selectNode(self, index):
        if index > self.size:
            return 'overflow'
        else:
            target = self.head
            count = 1
            while count < index:
                target = target.next
                count += 1
            return target

    def deleteNode(self, index):
        if index < 1:
            return 'underflow'
        elif index > self.size:
            return 'overflow'

        if index == 1: # 맨 앞 노드 삭제
            tmp = self.selectNode(1)
            self.head = self.head.next
            del tmp
            self.head.prev = self.tail
            self.tail.next = self.head
        elif index == self.size: # 맨 뒤 노드 삭제
            tmp = self.selectNode(self.size - 1)
            self.tail = tmp
            del self.tail.next
            self.tail.next = self.head
            self.head.prev = self.tail
        else: # 중간의 노드 삭제
            tmp = self.selectNode(index - 1)
            tmp.next = tmp.next.next
            tmp.next.next.prev = tmp
            del_node = tmp.next
            del del_node
        self.size -= 1

        if self.size == 1:
            self.head.next = self.head.perv = None
            self.tail.next = self.tail.prev = None

    def sizePrt(self):
        print(self.size)
        return

출처

• https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
• https://daimhada.tistory.com/72?category=820522