Base Algorithm with Python #2

1 . Linked List

 

Linked List는 대부분의 알고리즘에서 사용하는 자료구조이다. 알고리즘에서 사용하는 데이터와 다음 노드(Node)를 가리키는 링크(Link)를 묶어 노드로 정의해 사용한다. C 혹은 C++의 개념에서는 포인터 개념을 링크로 사용하지만 파이썬은 해당 개념이 존재하지 않는다.

 

우선 용어부터 알아보자. 연결리스트에는 기본적으로 링크와 노드 라는 용어를 사용한다.

파이썬에서 연결리스트를 사용하기 위해서는 노드를 클래스로 정의하여 사용한다.

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

이 클래스의 경우 호출 시 __init__메서드를 호출하고 Node라는 클래스는 data와 link라는 멤버를 가지고 있다. 여기서 data 는 데이터를 저장하는것이고 link라는 멤버는 링크를 저장하는 멤버이다

다음 그림은 노드를 가리키는 링크만 존재한다. A는 B를 B는 C를 최종적으로 가리키는것을 볼 수 있다. 이와 같이 자신의 노드에서 다음 노드를 가리키는 것이 전형적인 Linked List형식이다.

Linked List는 자료를 저장하는 하나의 자료구조일 뿐이다. 기본적인 파이썬 배열(List)과 거의 동일하다. 그러면 배열 대신 Linked list를 쓰는 이유는 무엇일까? 그 이유는 연결리스트의 장점이 배열의 단점이 되기 때문이다.

배열은 동일한 자료형을 갖는 데이터들의 집합이다(리스트라는 자료형). 또한 이 특성은 연속적이라는 것인데 배열을 생성할 때는 한번에 총 메모리를 확보해 사용할 수 있도록 하기 때문에 프로그램 중간에 배열의 크기를 바꿀 수 없다.

 

배열의 단점은 배열 안에 저장되어 있는 값들을 정렬할 때도 일일이 메모리에 저장된 값을 바꿔 줘야 한다는 것이다. 아까 말했듯이 Linked List의 장점은 배열의 단점이 된다고 했다. 배열은 연속된 메모리를 사용한다. 여기서 연속된 메모리라 하는 것은 프로세스들에게 연속된 메모리가 할당된다는 것이다.

 

하지만 Linked List는 꼭 연속적이라고는 못한다. 다르게 말하자면 Linked List는 연속적이지 않는 데이터들을 링크로 서로 연결하는거라 보면 된다.

 

위에서 Node A는 B를 Node B는 C를 가리키는 그림을 보았다 그렇다면 해당 그림을 코드로 옮겨보자.

왼쪽이 위쪽 그림에 대한 코드이며 오른쪽인 해당 코드의 결과값이다.

(참고

https://github.com/J-Hoplin/Algorithm-with-Python/blob/master/3%20.%20Linked%20List/1%20.%20Linked%20List.py

코드를 보고오자)

해당 코드를 읽을 수 있는 사람들은 해석해 보자.

이 부분은 각각 A,B,C라는 데이터 값을 갖는 클래스 객체들을 생성하여 객체에 저장한다

그 후 각각 노드(node_)의 next 멤버에 다음 노드에 해당하는 노드를 저장해 준다. 이 부분이 바로 노드에서 다른 노드를 가리키도록 하는 링크(Link)를 생성하는 부분이 되는것이다.

2 . Linked List Intersection Algorithm

 

(코드 : https://github.com/J-Hoplin/Algorithm-with-Python/blob/master/3%20.%20Linked%20List/2%20.%20Linked%20List%20Intersection.py)

 

해당 코드는 Linked List 삽입 알고리즘의 예시 코드이다. 우리가 여기서 눈여겨 봐야할  코드는 데이터를 삽입하는 부분인 이 코드이다.

이 코드를 분석해 보자. 우선적으로 inset()라는 함수는 인자로 data를 받는다. 그 후 앞에서 초기화 하는데에 쓰였던 node_a를 global을 통한 전역변수 처리를 한 다음 node_q와 node_w를 새로 생성하고 각각 node_a를 대입해준다. 여기서 node_q와 node_w를 생성한 이유는 연결 리스트를 탐색하면서 새로운 노드를 삽입할 노드의 위치를 보관하기 위함이다.

 

그 후 while문을 통해 node_w의 data멤버와 인자로 받은 data값을 비교하여 결과가 더 작으면 node_w는 다음 링크의 노드를 가리키도록 한다.(밑에 코드가 그 부분)

그 다음 node_w.data가 인수로 받은 data보다 크게 되면 해당 위치가 인수로 받은 data를 사용해 만든 new(새로운 노드)가 삽입될 위치가 되는것이다. 위치가 정해졌으니 그 다음에는 해당 위치에 대한 링크를 연결해 준다.

새로 삽입한 노드의 next멤버는 node_w를 가리키게 하고 node_w의 이전 노드에 해당하였던 node_q의 next에는 새로 삽입한 노드인 new 를 가리키게 한다.

 

혹시라도 이해가 안된 사람을 위해 분석한 그림을 보자.

3 . Insertation alogrithm에 대한 분석

 

1) 시간의 효율성

데이터나 노드를 삽입하기 위해서는 삽입할 데이터의 위치 검색 과정과 실제 데이터를 삽입하는 과정이 필요하다. 이러한 점에서 연결리스트는 배열에 비해 시간 효율성이 훨씬 높다. 삽입 위치 검색 과정에서는 배열과 연결리스트의 큰 차이점은 없다. 하지만 데이터를 삽입하는 과정에서는 전체 배열 크기와 연결리스트의 노드 수가 많으면 많을수록 큰 차이를 보여준다.

2) 공간의 효율성

배열은 프로그램 실행 도중에 크기를 변경시키지 못해 공간 효율성이 매우 떨어진다. 반면에 연결리스트는 필요할때마다 동적 공간을 할당해 사용할 수 있기 때문에 공간의 효율성이 뛰어나다.

3)코드의 효율성

코드의 효율성은 배열이 더 나을 수도 있다. 여기서 코드의 효율성이란 진입장벽을 의미하는데, 배열 같은 경우는 이해 및 활용이 간단하지만 연결리스트는 배열만큼 진입장벽이 낮지 않다.

 

4 . Linked List Delete Algorithm

 

(코드

https://github.com/J-Hoplin/Algorithm-with-Python/blob/master/3%20.%20Linked%20List/3%20.%20Linked%20List%20Delete%20Algorithm.py)

 

코드를 보면 Insertation 알고리즘 코드에서 달리진거는 

이 코드가 추가 되었다는 점일 것이다. 이말은 즉슨 해당 코드 부분이 삭제 알고리즘에 해당한다는 소리이다.

 

위의 삽입 알고리즘과 동일하게 global로 연결리스트가 담긴 node_a를 전역 변수 처리를 하여 사용한다. 이 연결리스트(node_a)를 의미하는 pre를 선언하고 pre가 링크를 통해 가리키고 있는 다음 노드(node_a.link)를 의미하는 next를 선언한다.

첫번째 if문부터 살펴보자. 첫번째 노드인 pre가 삭제할 함수(인자 dele)와 같은 값을 가지고 있다고 가정하자. 그렇다면 pre라는 노드가 가장 처음의 노드인데 삭제해야하는 상황이므로 이는 해당 delete함수에서가 아닌 이 프로그램 전체에서 pre가 의미하는 node_a의 값에 영향을 줘야하는 상황이므로 node_a에 next(node_a.list = node_b)를 넣어준다. 그 후 현재 지정 노드인 pre를 삭제하고 return 을 통해 함수를 리턴한다.

그 다음 두번째 while문을 살펴보자

앞에서의 if문은 만약 첫번째 노드가 없애고자 할때의 노드인것인 반면 이 while문은 삭제하고자 하는 노드가 두번째 이상일 경우 부터이다. 여기서 while next: 라는 문의 의미는 next라는 노드가 존재할때까지 while문을 반복하겠다는 의미이다. 즉 만약 next라는 노드가 없어질 경우 Boolean은 True -> False가 되어 while문에서 나오게 된다. Next의 데이터가 만약 삭제하고자 하는 노드와 동일하다고 가정하자.

이럴 경우 next의 이전노드인 pre노드가 .link멤버를 통해 가리키고 가리키고 있던 것이 next노드에서 next노드의 다음 노드가 되어야 한다. 여기서 next노드의 다음 노드를 다르게 표현해보면 next.link가 된다. 이 next.link값을 pre.link값에 대입하여 pre노드가 링크로 가리키는 노드를 변환시켜주고 next노드를 삭제 시켜준 다음 while문을 나가준다.

저 밑의 pre = next와 next = next.link는 그림으로 설명하겠다.

여기 까지 이해가 되었다면 기존 삽입 알고리즘에 삭제 알고리즘을 더하고

Print(‘D노드 삭제’)

Delete(‘D’)

Result()

를 넣고 실행해보자 그러면 결과는 다음과 같이 나온다

5 . Delete Algorithm 분석

1) 시간 효율성 : 삽입, 삭제 알고리즘 모두 삭제 및 삽입할 노드를 검색하는 과정과 실행하는 과정이 필요하다. 노드 삭제의 경우 배열은 삭제해야할 노드를 삭제한 후 삭제 이후 데이터를 모두 앞으로 끌어야하는 불편함이 있는 반면 Linked List는 링크를 끊어주고 삭제할 노드만 해제해 주면 된다.

2) 공간 효율성 : 삽입 알고리즘과 마찬가지로 메모리를 할당 및 해제하는 동적 메모리 개념이 쓰이므로 공간 효율성이 배열에 비해 좋다.

3) 코드 효율성 : 이 또한 진입장벽 면에서 배열이 낮기 때문에 배열이 코드 효율성은 더 좋다.