[Section 2] 연결 리스트 _ 중간 삽입& 삭제 구현

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

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

0. INTRO

지금까지 연결 리스트의 노드 생성과 삽입, 그리고 삭제를 통해서 어떻게 연결 리스트가 구성되는지 알아보았다. 이번에는 중간 삽입 기능을 구현하여, 연결 리스트 자료구조를 완전히 이해하도록 하자.

1. 중간 삽입 방법 _ 위치 함수의 필요성

리스트에 중간 삽입을 하는 방법은 의외로 간단하다. 연결된 링크를 끊어주고 새 노드를 붙이면 된다. 하지만 지금까지 구현한 SLL함수는 위치를 나타내는 기능이 없기 때문에 가장 먼저 위치함수를 구현하는 것이 필요하다. 

 

중간 삽입 동작 개요도

 

특정 노드의 위치를 지정하는 위치 함수를 구현하기전에 리스트에서 자주 등장하는 인덱싱(Indexing)과 슬라이싱(Slicing)용어를 알고 넘어가자. 파이썬 기본 문법 중 리스트 문법에서는 특정 원소 만을 추출하기 위해서 인덱스(index)라는 일종의 주소 변수를 사용했는데, 이렇게 특정 원소에 접근하는 것을 인덱싱이라고 한다. 그리고 슬라이싱은 리스트의 부분 원소만을 추출하는 것을 이야기한다. 그렇다면, 위치 함수는 일종의 인덱싱 기능의 구현이라고 할 수 있다. 

2.  중간 삽입 기능 알고리즘

만약 중간 삽입하는 위치가 첫 부분 혹은 마지막 부분이라면, 굳이 노드를 복잡하게 이어 붙이는 작업을 안해주어도된다. 따라서 다음의 코드는 위치가 첫 부분과 끝 부분을 향할 때 기존의 삽입 방식을 선택하는 코드이다.

 

예시 코드:

    def insertP(self,pos,data):
        if pos > self.length or pos <0:
            return None
        else:
            if pos == 0:
                self.insertF(data)
            else:
                if pos == self.length:
                    self.insetL(data)

중간 부분에 삽입을 위한 절차를 생각해보면, 먼저 새 노드 생성, 그리고 기존 리스트에서 해당 위치에 접근을 해야 한다. 그리고 해당 위치의 node는 새 노드를 가리켜야 하고 새 노드의 node는 끊어준 나머지 리스트를 가리키면 된다. 다음의 예시 코드를 참고하자.

 

예시 코드:

    def insertP(self,pos,data):
        if pos > self.length or pos <0:
            return None
        else:
            if pos == 0:
                self.insertF(data)
            else:
                if pos == self.length:
                    self.insetL(data)
                else:
                    N=Node(data)
                    count = 0
                    now = self.head
                    while count < pos -1:
                        count +=1
                        now = now.getN()
                    N.setN(now.getN())
                    now.setN(N)
                    self.length +=1

 

 

중간 삽입 결과

* 중간 삭제기능은 따로 구현하지 않겠으나, 중간 삽입과 동일한 원리로 구현하면 된다. 다만 리스트의 전체 길이가 1 줄어들어야 하는 것을 명시하자.