[자료구조] 링크드(연결) 리스트(Linked List) -Data Structure with 파이썬

링크드(연결) 리스트(Linked List)

왜?

배열의 경우로 데이터를 넣었을 때 미리 공간을 정해놓아야한다. 만약 데이터가 너무 커서 공간을 넘어가서 데이터가 끊어지게 되면 안되기 때문에 연결리스트가 나오게 된 이유가 있다.

 

 - 노드를 연결시킨 자료구조

 

 - 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

 

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

위 그림처럼 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당함.

 

C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

 

 

• 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
• 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

링크드(연결) 리스트(Linked List)의 핵심연산

• add(or insert)
  • 삽입인데 맨 뒤가 아닌 중간에 삽입하는 것도 해야함.
• remove
  • 삭제
• count
  • 연결리스트에 저장되어 있는 데이터의 수

 

종류

• 단일 연결 리스트 , 이중 연결 리스트 , 원형 연결 리스트

단일, 이중, 원현 순서  https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

장단점

• 장점
  • 미리 데이터 공간을 미리 할당하지 않아도 됨
    • 배열은 미리 데이터 공간을 할당 해야 함
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

연결리스트 구현 (파이썬 클래스를 활용)

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

class HeadNode:
    def __init__(self,next=None):
        self.count=0
        self.head=next

    def add(self,data):
        node_data = self.head
        while node_data.next is not None:
            node_data=node_data.next
        node_data.next=Node(data)
        self.count += 1

    def print_all(self):
        node_data=self.head
        while node_data is not None:
            print(node_data.data)
            node_data=node_data.next

one=HeadNode(Node(1))
one.add(2)
one.add(3)
one.print_all()

'''
1
2
3
'''

추가 - 연결리스트 중간에 노드 추가하기 + 중간 마지막 처음 부분 삭제하기

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

class HeadNode:
    def __init__(self,data):
        self.count=0
        self.head=Node(data)

    def get_node(self,index):
        cnt=0
        node=self.head
        while cnt<index:
            node=node.next
            cnt+=1
        return node

    def add(self,data,index=None):
        new_node=Node(data)
        if index is None:
            node_data = self.head
            while node_data.next is not None:
                node_data = node_data.next
            node_data.next = new_node
        elif index<0 or (index>self.count+1):
            print('wrong index :', index)
            del new_node
        else:
            before_node = self.get_node(index-1)
            temp=before_node.next
            before_node.next=new_node
            new_node.next=temp

        self.count += 1


   def delete(self, data):
        node = self.head
        if not node:
            print('해드노드가 없습니다.')
        elif node.data==data:
            temp=node.next
            del node
            self.head=temp
            print('해드노드가 삭제되었습니다.')
            print('새로운노드가 {}로 등록되었습니다.'.format(self.head.data))
        else:
            while node.next:
                if (node.next).data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    self.count -= 1
                    return
                else:
                    node = node.next

            if not node.next:
                print('wrong data: ', data)
                

    def print_all(self):
        node_data=self.head
        while node_data is not None:
            print(node_data.data)
            node_data=node_data.next

one=HeadNode(1)
one.add(2)
one.add(3)
one.add(4,1)
one.add(5,2)
one.add(6,7)
one.add(6,5)
one.delete(1)
one.print_all()

'''
wrong index : 7
해드노드가 삭제되었습니다.
새로운노드가 4로 등록되었습니다.
4
5
2
3
6
'''

 

하루가 지나고 수정하였다.

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

class Headnode:
    def __init__(self,data):
        self.count=0
        self.head=Node(data)

     def add(self,data,index=None):
        new_node=Node(data)
        if not index:
            node_data = self.head
            while node_data.next is not None:
                node_data = node_data.next
            node_data.next = new_node
        elif index<0 or (index>self.count+1):
            print('wrong index :', index)
            del new_node
        else:
            before_node = self.get_node(index-1)
            temp=before_node.next
            before_node.next=new_node
            new_node.next=temp

        self.count += 1

    def delete(self,data):
        if self.head is None:
            print('앞에서 해드노드까지 다 삭제 되어 삭제 할수 없습니다.')
            return

        if self.head.data==data:
            temp=self.head
            self.head=self.head.next
            del temp
            print('데이터 : {}가 삭제되었습니다.'.format(data))
            self.count -= 1
        else:
            node = self.head
            while node.next is not None:
                if node.next.data==data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    print('데이터 : {}가 삭제되었습니다.'.format(data))
                    self.count -= 1
                    return
                node=node.next

    def print_all(self):
        node=self.head
        while node is not None:
            print(node.data)
            node=node.next

 

더블 연결리스트

특정 인덱스에 추가하는 것으로 구현했다. 그리고 삭제에 있어서는 그냥 앞에서부터 쭉 오면서 입력한 데이터가 있다면 그 데이터를 삭제하는 것으로 구현했다.

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

class Headnode:
    def __init__(self,data):
        self.head=Node(data)
        self.tail=Node(data)
        self.count=1

    def add(self,data,index=-1):
        if index-self.count>=2:
            print('잘못된 인덱스입니다.')
            return
        new_node = Node(data)
        if self.head is None:
            self.head=new_node
            self.tail = new_node
            self.count = 1
        else:
            node=self.head
            cnt=0
            while node.next is not None:
                if cnt==index-2:
                    temp=node.next
                    temp.prev = new_node
                    node.next = new_node
                    new_node.next = temp
                    new_node.prev = node
                    self.tail=new_node
                    return
                node=node.next
                cnt+=1
            node.next=new_node
            new_node.prev=node
            self.tail=new_node
        self.count+=1

    def delete(self,data):
        if self.head is None:
            print('이미 해드노드가 삭제 되었습니다.')
        if self.head.data==data:
            temp=self.head
            self.head=self.head.next
            del temp
            print('해드노드가 삭제 되었습니다.')
        else:
            node = self.head
            while node.next:
                if node.next.data==data:
                    temp=node.next
                    node.next=node.next.next
                    node.next.prev=node
                    del temp
                    break
                node=node.next
            if node.next is None:
                print('해당하는 값은 더블링크드리스트에 없습니다.')


    def print_all(self):
        node=self.head
        while node is not None:
            print(node.data)
            node=node.next