[Section 2] 연결 리스트의 삽입(Insert) _ 첫 부분과 끝

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

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

0. INTRO

이번에는 연결 리스트의 주요 기능인 삽입(Insert) 기능을 구현하고자 한다. 삽입 기능은 헤드 부분, 중간, 그리고 꼬리 부분에 삽입하는 기능으로 나누어질 수 있다. 여기에서는 클래스 유형으로 연결 리스트와 그 삽입 기능을 정의하 고사용 하고자 한다.

1. 헤드 포인터 이해 _ 클래스 내부에 클래스 생성하기

지금까지는 SSL 클래스를 선언하고, 헤드 변수를 따로 이해하지 않았다. 노드를 생성할 수 있다면, 그것은 특정 변수가 클래스를 지정하는 포인터가 된다는 것이고, 그것은 변수에 노드 블록의 주소를 할당해 주는 의미를 가지고 있다. 가시적으로는 다음의 그림과 같은 의미다.

 

헤드 포인터 변수의 의미

 

위의 기능을 위해서 SLL 클래스를 다음과 같이 새로 만들어보자. 

 

예시 코드:

class SLL:
    def __init__(self,head = None,node=None):
        self.head=head
        self.node=node

        self.length=0

 

헤드 개념의 이해

 

위 프로그램의 동작 개요를 보면 헤드가 어떤 역할을 하는지 알 수 있다. 다음은 SLL함수에 데이터를 삽입하고 삭제하는 기능을 추가하자. 

2. 연결 리스트의 삽입 _ 첫 부분에 삽입하기

첫 부분과 끝부분에 새로운 데이터를 삽입하거나 기존의 데이터를 삭제하는 기능을 구현하는 것은 헤드 포인터가 있다면 비교적 간단하다. 다음의 예시 코드를 보자.

 

예시 코드:

    def insertF(self,data):
        N=Node(data)
        if self.length == 0:
            self.head=N
        else:
            N.setN(self.head)
            self.head=N
        self.length +=1

코드 결과:

삽입 동작 개요

2. 연결 리스트의 삽입 _ 끝 부분에 삽입하기

리스트 꼬리 부분에 노드를 삽입하는 것은 반복문과 조건문을 필요로 한다.

다음의 예시 코드를 참고하자.

 

예시 코드:

    def insertF(self,data):
        N=Node(data)
        if self.length == 0:
            self.head=N
        else:
            N.setN(self.head)
            self.head=N
        self.length +=1
    def insertL(self,data):
        N=Node(data)
        if self.length == 0:
            self.head=N
        else:
            now=self.head
            while now.getN() !=None:
                now=now.getN()
            now.setN(N)
        self.length +=1

 

코드 결과:

끝 부분 삽입 개요

 

* 첫 부분과 끝 부분 삽입을 통해서 데이터의 구성이 어떻게 차이가 나는지 이해하고 넘어가자!