[Section 2] 연결 리스트(Singly Linked List) _ 노드 삭제 기능 구현

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

이번에는 연결 리스트의 헤드 부분과 꼬리 부분에 데이터를 삭제 기능을 클래스를 이용하여 구현해보도록 하자. 노드 생성 및 클래스 함수 코드는 이전에 직접 정의한 SLL() 함수를 참고하면 된다. 

1. 모든 데이터 삭제 _ 연결 리스트의 초기화 구현

연결 리스트에 존재하는 모든 데이터를 삭제하는 것은 매우 간단하다. 바로 리스트의 헤드 데이터를 초기화하도록 하면 되는데, 이 기능은 연결 리스트의 데이터 개수에 상관없이 시간 복잡도와 공간 복잡도가 O(1)이라는 장점을 가지고 있다. 데이터를 접근할 필요가 없기 때문이다. 다음의 예시 코드를 참고하고, 데이터 삭제 함수를 이해해보자.

 

예시 코드:

    def clear(self):

        self.head=None

        self.length=0

 

* 임의로 2 노드를 가진 연결 리스트를 만들고 위 함수를 사용해보자.

 

연결 리스트 초기화 구현

2. 노드 삭제 기능 구현하기 _ 헤드 부분 노드 순서로 삭제하기

처음부터 차례대로 연결 리스트를 학습해왔다면, 이제 포인터의 역할과 연결 리스트 자료 구조에 대한 이해가 쉽게 될 것이다. 구현 또한 어떻게 해야 할지 어느 정도 감이 왔을 거라고 판단된다. 그렇다면, 다음의 예시 코드로 헤드 부분 순서로 차례대로 삭제하는 기능을 이해해보자.

 

예시 코드:

    def delete(self):
        if self.length == 0:
            pass
        else:
            self.head=self.head.getN()
            self.length -=1

 

코드 결과 :

연결 리스트 _ 앞부분 삭제 기능 구현

3. 노드 삭제 기능 구현하기 _ 꼬리 부분 순서로 노드 삭제하기

삽입 기능과 마찬가지로 꼬리 부분에 접근하기 위해서는 반복문과 조건문을 이용해야한다. 따라서 다음과 같은 접근 방법을 제시한다. 

 

예시 코드:

    def delete2(self):
        if self.length == 0:
            pass
        else:
            now= self.head
            before=self.head
            while now.getN() !=None:
                before=now
                now=now.getN()
            before.setN(None)
            self.length -=1

 

연결 리스트 _ 끝부분 삭제 기능 구현