단순 연결 리스트의 개념과 간단구현

 1  단순 연결 리스트의 개념

저번에 배운 선형 리스트는 배열에 데이터를 차례대로 저장하므로 데이터의 실제 위치 순서로 구성된다.

반면에 단순 연결 리스트(Singly Linked List)는 저장된 노드들이 물리적으로 떨어진 곳에 위치하게 된다,

각 노드의 번지도 순차적이지 않다. 하지만 연결(Link)을 따라가 보면 순서대로 노드를 계속 가리키게 된다.

선형리스트는 배열에 구성했기에 단순하고, 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간편하다.

하지만 데이터를 삽입하거나 삭제하기는 많은 작업이 필요하다(Overhead 가 발생하기 쉽다).

단순 연결 리스트에선 이런 단점을 보안해 데이터를 삽입하거나 삭제하는 과정이 비교적 간단하다(Overhead 가 거의 발생하지 않는다).

 

 2  단순 연결 리스트의 원리

단순 연결 리스트를 구현하려면 우선 '노드'의 개념을 파악해야 한다. 

단순 연결 리스트는 다음 데이터를 가리키는 링트(Link)가 더 필요하다. 데이터뿐만 아니라 다음 데이터를 가리키는 화살표 개념의 링크도 같이 저장해야 하는 것이다. 이렇게 데이터와 링크로 구성된 항목을 노드(Node)라고 한다.

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

node1 = Node()
node1.data = "다현"
print(node1.data, end = ' ')

노드를 파이썬에서 구현하는 코드이다. 파이썬에선 노드 모양의 데이터형이 없기에 클래스라는 문법을 사용하여 Node 데이터형을 정의한 것이다. 노드를 생성할 때 자동으로 데이터와 링크가 저장되도록 하는 것이다.

또 단순 연결 리스트에선 첫 번째 노드를 가리키는 헤드(head)를 사용한다.

단순 연결리스트가 한쪽 방향으로만 진행되어 다음 노드로는 찾아갈 수 있지만 이전 노드로는 돌아갈 수 없는데, 헤드를 이용하여 처음부터 다시 진행하는 것이다.

예시로 5명으로 구성된 단순 연결 리스트를 구현하면서 작동원리를 이해하자

## 데이터가 5개인 단순 연결 리스트 생성 ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"

node2 = Node()
node2.data = "정연"
node1.link = node2

node3 = Node()
node3.data = "쯔위"
node2.link = node3

node4 = Node()
node4.data = "사나"
node3.link = node4

node5 = Node()
node5.data = "지효"
node4.link = node5

print(node1.data, end = ' ')
print(node1.link.data, end = ' ')
print(node1.link.link.data, end = ' ')
print(node1.link.link.link.data, end = ' ')
print(node1.link.link.link.link.data, end = ' ')

마지막 print문들을 보면 저런 식으로 첫 번째 노드를 기준으로 마지막 노드까지 전체를 접근하고 출력할 수 있다.

이런 원리를 이용해 다른 식으로 노드의 처음부터 끝까지 출력하는 함수를 작성할 수 있다.

## 데이터가 5개인 단순 연결 리스트 생성(개선 버전) ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"

node2 = Node()
node2.data = "정연"
node1.link = node2

node3 = Node()
node3.data = "쯔위"
node2.link = node3

node4 = Node()
node4.data = "사나"
node3.link = node4

node5 = Node()
node5.data = "지효"
node4.link = node5

current = node1
print(current.data, end = ' ')
while current.link !=None :
    current = current.link
    print(current.data, end = ' ')

 

첫 번째 노드를 현재(current) 노드를 지정해 출력하고 노드의 링크가 비어 있지 않는 동안 반복하는 원리이다.

 

 3  노드 삽입

앞에서 생성한 단순 연결 리스트의 중간에 데이터를 삽입 해보자.

단순 연결 리스트에서 노드 삽입의 원리는 이렇다. 

1. 새 노드를 생성하고 데어터를 넣는다.
2. 새 노드의 링크에 삽입할 위치 전 노드의 링크를 복사한다. ( 새 노드와 전 노드가 모두 앞 노드를 가리키고 있는 상태)
3. 전 노드의 링크를 새 노드에 지정한다.

코드로 구현하면 아래처럼 구현된다.

## 단순 연결 리스트의 노드 삽입 ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"

node2 = Node()
node2.data = "정연"
node1.link = node2

node3 = Node()
node3.data = "쯔위"
node2.link = node3

node4 = Node()
node4.data = "사나"
node3.link = node4

node5 = Node()
node5.data = "지효"
node4.link = node5

newNode = Node()
newNode.data = "재남"
newNode.link = node2.link
node2.link = newNode

current = node1
print(current.data, end = ' ')
while current.link !=None :
    current = current.link
    print(current.data, end = ' ')

newNode 가 나오는 시점부터 4줄이 삽입부분이다.

 

 4  노드 삭제

단순 연결 리스트의 중간에 데이터를 삭제 해보자.

단순 연결 리스트에서 노드 삭제의 원리는 이렇다.

1. 삭제할 노드에 전 노드의 링크를 삭제 할 노드 앞 노드의 링크로 복사한다.
2. 링크가 되어 있지 않은 삭제할 노드를 삭제한다.

코드로 구현하면 아래처럼 구현된다.

## 단순 연결 리스트의 노드 삭제 ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"

node2 = Node()
node2.data = "정연"
node1.link = node2

node3 = Node()
node3.data = "쯔위"
node2.link = node3

node4 = Node()
node4.data = "사나"
node3.link = node4

node5 = Node()
node5.data = "지효"
node4.link = node5

node2.link = node3.link
del(node3)

current = node1
print(current.data, end = ' ')
while current.link !=None :
    current = current.link
    print(current.data, end = ' ')

del()은 노드를 삭제하는 함수이다.