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

Link

Today

Total

Recent Posts

Recent Comments

Archives

« 2024/04 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Tags more

Notice

관리 메뉴

반원 블로그

02c. 이중 연결 리스트(doubly linked list) - iv. 삭제 본문

2018~/파이썬 자료구조 알고리즘

02c. 이중 연결 리스트(doubly linked list) - iv. 삭제

반원_SemiCircle 2019. 5. 5. 02:36

삭제

삽입과 마찬가지로 삭제 또한 head를 통한, tail을 통한 삭제 2가지가 있습니다.

저장된 노드가 없을 때

당연히 삭제연산 경우에서 제외시켜야됩니다.

#이중 링크드 리스트 
class DLinkedList: 

    #D_L_list에서 쓸 노드 
    class Node: 
        def __init__(self, v, n = None, p = None): 
            self.value = v #저장된 데이터 
            self.next = n #다음 노드 가리키는 변수 
            self.prev = p #이전 노드 가리키는 변수 

    #D_L_List에서 필요한 변수 
    def __init__(self): 
        self.head = None #첫 생성시 내부에는 노드가 없으므로 
        self.tail = None 

    #head로 삽입. v : 데이터 
    def insertNodeBefore(self, v): 
        #없을 경우 
        if self.head is None: 
            self.head = self.Node(v) 
            self.tail = self.head #같은 노드를 가리킴 
        else: 
            #self.head : 기존노드, self.head.prev : 기존노드의 prev 
            self.head.prev = self.Node(v,n=self.head) #1,2번을 동시수행 
            #self.head.prev : 기존노드의 prev == 새로운 노드 
            self.head = self.head.prev #3. head를 새로운 노드로 변경 

    #tail로 삽입. v : 데이터 
    def insertNodeAfter(self, v): 
        #없을 경우 
        if self.tail is None: 
            self.tail = self.Node(v) 
            self.head = self.tail #같은 노드를 가리킴 
        else: 
            #self.tail : 기존노드, self.tail.next : 기존 노드의 next 
            self.tail.next = self.Node(v,p=self.tail) #1,2번을 동시수행 
            #self.tail.next : 기존노드의 next == 새로운 노드 
            self.tail = self.tail.next #3. tail를 새로운 노드로 변경 

    def printNodeBefore(self): 
        #데이터가 없을 때 
        if self.head is None: 
            print("저장된 데이터가 없음") 
            return 
        else: 
            print("<현재 리스트 구조>", end='\t') #end로 print 마지막 개행을 변경할 수 있습니다. 
            link = self.head #처음은 head를 지정. 이후부터는 현 노드의 next를 지정 

            #link가 가리키는 노드가 없을 때까지 반복 
            #None,0,""는 조건판단에서 False 처리, 그 외는 True로 처리된다. 
            while link : 
                print(link.value, '<->' , end = ' ') 
                link = link.next #link를 현 위치 노드의 next로 변경 
            print() #줄바꿈 용 

    def printNodeAfter(self): 
        #데이터가 없을 때 
        if self.tail is None: 
            print("저장된 데이터가 없음") 
            return 
        else: 
            print("<현재 리스트 구조>", end='\t') 
            link = self.tail 

            while link : 
                print(link.value, '<->' , end = ' ') 
                link = link.prev #link를 현 위치 노드의 next로 변경 
            print() #줄바꿈 용 

    #head로 삭제 
    def deleteNodeBefore(self): 
        #없을 경우 - > 스킵 
        if self.head is None : 
            print("삭제할 노드가 없습니다.") 
            return 

    #tail로 삭제 
    def deleteNodeAfter(self): 
        #없을 경우 - > 스킵 
        if self.tail is None : 
            print("삭제할 노드가 없습니다.") 
            return 

##테스트 
if __name__=="__main__": 
    dl = DLinkedList() 
    dl.deleteNodeBefore() 
    dl.deleteNodeAfter()

저장된 노드가 있을 때(head)

head를 통해 노드를 삭제할 경우, 곧 head가 될 노드의 prev는 None으로 변경해줘야합니다.

따라서 다음 수행절차를 진행하겠습니다.

현재 head가 가리키는 노드의 next를 새로운 head로 지정
새로운 head의 prev를 None으로 변경

###코드 구현

#이중 링크드 리스트 
class DLinkedList: 

    #D_L_list에서 쓸 노드 
    class Node: 
        def __init__(self, v, n = None, p = None): 
            self.value = v #저장된 데이터 
            self.next = n #다음 노드 가리키는 변수 
            self.prev = p #이전 노드 가리키는 변수 

    #D_L_List에서 필요한 변수 
    def __init__(self): 
        self.head = None #첫 생성시 내부에는 노드가 없으므로 
        self.tail = None 

    #head로 삽입. v : 데이터 
    def insertNodeBefore(self, v): 
        #없을 경우 
        if self.head is None: 
            self.head = self.Node(v) 
            self.tail = self.head #같은 노드를 가리킴 
        else: 
            #self.head : 기존노드, self.head.prev : 기존노드의 prev 
            self.head.prev = self.Node(v,n=self.head) #1,2번을 동시수행 
            #self.head.prev : 기존노드의 prev == 새로운 노드 
            self.head = self.head.prev #3. head를 새로운 노드로 변경 

    #tail로 삽입. v : 데이터 
    def insertNodeAfter(self, v): 
        #없을 경우 
        if self.tail is None: 
            self.tail = self.Node(v) 
            self.head = self.tail #같은 노드를 가리킴 
        else: 
            #self.tail : 기존노드, self.tail.next : 기존 노드의 next 
            self.tail.next = self.Node(v,p=self.tail) #1,2번을 동시수행 
            #self.tail.next : 기존노드의 next == 새로운 노드 
            self.tail = self.tail.next #3. tail를 새로운 노드로 변경 

    def printNodeBefore(self): 
        #데이터가 없을 때 
        if self.head is None: 
            print("저장된 데이터가 없음") 
            return 
        else: 
            print("<현재 리스트 구조>", end='\t') #end로 print 마지막 개행을 변경할 수 있습니다. 
            link = self.head #처음은 head를 지정. 이후부터는 현 노드의 next를 지정 

            #link가 가리키는 노드가 없을 때까지 반복 
            #None,0,""는 조건판단에서 False 처리, 그 외는 True로 처리된다. 
            while link : 
                print(link.value, '<->' , end = ' ') 
                link = link.next #link를 현 위치 노드의 next로 변경 
            print() #줄바꿈 용 

    def printNodeAfter(self): 
        #데이터가 없을 때 
        if self.tail is None: 
            print("저장된 데이터가 없음") 
            return 
        else: 
            print("<현재 리스트 구조>", end='\t') 
            link = self.tail 

            while link : 
                print(link.value, '<->' , end = ' ') 
                link = link.prev #link를 현 위치 노드의 next로 변경 
            print() #줄바꿈 용 

    #head로 삭제 
    def deleteNodeBefore(self): 
        #없을 경우 - > 스킵 
        if self.head is None : 
            print("삭제할 노드가 없습니다.") 
            return 
        else: 
            #1.현재 head가 가리키는 노드의 next를 새로운 head로 지정 
            self.head = self.head.next 
            #2. 새로운 head의 prev를 None으로 변경 
            self.head.prev = None 

    #tail로 삭제 
    def deleteNodeAfter(self): 
        #없을 경우 - > 스킵 
        if self.tail is None : 
            print("삭제할 노드가 없습니다.") 
            return 

##테스트 
if __name__=="__main__": 
    dl = DLinkedList() 
    dl.insertNodeBefore('1stF') 
    dl.insertNodeAfter('1stB') 
    dl.insertNodeBefore('2ndF') 
    dl.insertNodeAfter('2ndB') 
    dl.printNodeBefore() 
    dl.deleteNodeBefore() #head로 삭제 
    dl.printNodeBefore()

저장된 노드가 있을 때(tail)

head 삭제방법과 방법은 일치합니다. 다만 head가 tail로, prev가 next로 n 변경될 뿐이죠.

따라서 다음 수행절차를 진행하겠습니다.

현재 tail가 가리키는 노드의 prev를 새로운 tail로 지정
새로운 tail의 next를 None으로 변경

###코드 구현

#이중 링크드 리스트 
class DLinkedList: 

    #D_L_list에서 쓸 노드 
    class Node: 
        def __init__(self, v, n = None, p = None): 
            self.value = v #저장된 데이터 
            self.next = n #다음 노드 가리키는 변수 
            self.prev = p #이전 노드 가리키는 변수 

    #D_L_List에서 필요한 변수 
    def __init__(self): 
        self.head = None #첫 생성시 내부에는 노드가 없으므로 
        self.tail = None 

    #head로 삽입. v : 데이터 
    def insertNodeBefore(self, v): 
        #없을 경우 
        if self.head is None: 
            self.head = self.Node(v) 
            self.tail = self.head #같은 노드를 가리킴 
        else: 
            #self.head : 기존노드, self.head.prev : 기존노드의 prev 
            self.head.prev = self.Node(v,n=self.head) #1,2번을 동시수행 
            #self.head.prev : 기존노드의 prev == 새로운 노드 
            self.head = self.head.prev #3. head를 새로운 노드로 변경 

    #tail로 삽입. v : 데이터 
    def insertNodeAfter(self, v): 
        #없을 경우 
        if self.tail is None: 
            self.tail = self.Node(v) 
            self.head = self.tail #같은 노드를 가리킴 
        else: 
            #self.tail : 기존노드, self.tail.next : 기존 노드의 next 
            self.tail.next = self.Node(v,p=self.tail) #1,2번을 동시수행 
            #self.tail.next : 기존노드의 next == 새로운 노드 
            self.tail = self.tail.next #3. tail를 새로운 노드로 변경 

    def printNodeBefore(self): 
        #데이터가 없을 때 
        if self.head is None: 
            print("저장된 데이터가 없음") 
            return 
        else: 
            print("<현재 리스트 구조>", end='\t') #end로 print 마지막 개행을 변경할 수 있습니다. 
            link = self.head #처음은 head를 지정. 이후부터는 현 노드의 next를 지정 

            #link가 가리키는 노드가 없을 때까지 반복 
            #None,0,""는 조건판단에서 False 처리, 그 외는 True로 처리된다. 
            while link : 
                print(link.value, '<->' , end = ' ') 
                link = link.next #link를 현 위치 노드의 next로 변경 
            print() #줄바꿈 용 

    def printNodeAfter(self): 
        #데이터가 없을 때 
        if self.tail is None: 
            print("저장된 데이터가 없음") 
            return 
        else: 
            print("<현재 리스트 구조>", end='\t') 
            link = self.tail 

            while link : 
                print(link.value, '<->' , end = ' ') 
                link = link.prev #link를 현 위치 노드의 next로 변경 
            print() #줄바꿈 용 

    #head로 삭제 
    def deleteNodeBefore(self): 
        #없을 경우 - > 스킵 
        if self.head is None : 
            print("삭제할 노드가 없습니다.") 
            return 
        else: 
            #1.현재 head가 가리키는 노드의 next를 새로운 head로 지정 
            self.head = self.head.next 
            #2. 새로운 head의 prev를 None으로 변경 
            self.head.prev = None 

    #tail로 삭제 
    def deleteNodeAfter(self): 
        #없을 경우 - > 스킵 
        if self.tail is None : 
            print("삭제할 노드가 없습니다.") 
            return 
        else: 
            #1.현재 tail이 가리키는 노드의 prev를 새로운 tail로 지정 
            self.tail = self.tail.prev 
            #2. 새로운 head의 prev를 None으로 변경 
            self.tail.next = None 

##테스트 
if __name__=="__main__": 
    dl = DLinkedList() 
    dl.insertNodeBefore('1stF') 
    dl.insertNodeAfter('1stB') 
    dl.insertNodeBefore('2ndF') 
    dl.insertNodeAfter('2ndB') 
    dl.printNodeBefore() 
    dl.deleteNodeBefore()  # head로 삭제 
    dl.printNodeBefore() 
    dl.deleteNodeAfter()  # tail로 삭제 
    dl.printNodeBefore()

위키독스 연재 : https://wikidocs.net/book/2868

저작자표시 비영리 변경금지

'2018~ > 파이썬 자료구조 알고리즘' 카테고리의 다른 글

03b. 성능 분석의 기준 (0)	2019.05.08
03. 성능분석 기법 (0)	2019.05.07
03a.자료구조와 알고리즘 (0)	2019.05.07
02c. 이중 연결 리스트(doubly linked list) - v. 탐색 (0)	2019.05.06
02c. 이중 연결 리스트(doubly linked list) - iii. 출력 (0)	2019.05.04
02c. 이중 연결 리스트(doubly linked list) - ii. 삽입 (0)	2019.05.03
02c. 이중 연결 리스트(Doubly linked list) - i. 구조 (0)	2019.05.02
02b. 단일 연결 리스트(singly linked list) - v. 탐색 (0)	2019.05.01

'2018~/파이썬 자료구조 알고리즘' Related Articles

Comments