자료구조 연결 리스트(SLL,DLL,CLL) -(1)SLL

단순연결리스트(Singly Linked List,SLL)

“단순 연결 리스트(SLL)” 이란, 동적 메모리 할당을 이용해 Node들을 한 방향으로 연결하여 리스트를 구현하는 자료구조이다.

리스트에는
Value값을 찾는 탐색연산,
새 Node와 Value를 추가하는 삽입연산,
항목을 제거하는 삭제연산 등이 있다.

이 SLL에서는 삽입이나 삭제시 Node들의 이동이 필요없다.
노드들은 차례대로 레퍼런스로 연결이 되어있다.

또한 탐색연산을 수행할 시 SLL은 항상 “첫 노드”부터 순차적으로 Target 값 까지 차례로 방문하는 순차탐색(Sequential Search)을 해야만 한다.

아래는 파이썬으로 작성한 코드 이다.

class SList:
    class Node:
        def __init__(self, item, link): #노드 생성자,*link는 연결할 곳
            self.item = item
            self.next = link
    
    def __init__(self): #생성자
        self.head = None
        self.size = 0

    def size(self): #링크드 리스트 크기 리턴 함수
        return self.size
    
    def is_empty(self): #링크드 리스트가 비었는지 boolean 값 리턴 함수
        return self.size == 0

    def insert_front(self, item): #리스트 맨 앞에 요소 추가 O(1)
        if self.is_empty(): #빈 리스트라면?
            self.head = self.Node(item, None) #None 레퍼런스를 가진 신 노드를 헤드로 지정.
        else: #비어있지 않은 리스트라면?
            self.head = self.Node(item, self.head) #헤드 레퍼런스를 가진 노드를 헤드로 갱신
        self.size += 1 #요소 추가로 크기 증가

    def insert_after(self, item, p): #특정 p가 가리키는 노드 뒤 요소 추가 O(1), 단 p가 안주어지면 O(N)- 탐색 필요
        p.next = self.Node(item, p.next) #우변 = p의 다음 레퍼런스를 가지고 있는 노드, 좌변 = p가 가르키는 노드의 다음 노드
        self.size += 1 #요소 추가로 크기 증가

    def delete_front(self): #맨 앞 노드를 삭제하는 함수 O(1)
        if self.is_empty():
            raise EmptyError('Underflow') #요소가 없는 경우 예외 처리
        else:
            self.head = self.head.next #맨 앞 노드 삭제는 단순히 헤드 노드 다음의 노드를 연결.
            self.size -= 1
    
    def delete_after(self, p): #p가 가르키는 노드의 다음노드를 삭제 O(1), 단 p가 안주어지면 O(N)- 탐색 필요
        if self.is_empty():
            raise EmptyError('Underflow') #요소가 없는 경우 예외 처리
        t = p.next #t가 p가 가르키는 노드의 다음노드라 할 때,
        p.next = t.next #p가 가리키는 노드의 다음노드가 t가 가르키는 다음노드가 되도록 연결하면 p가 가르키는 다음 노드,즉 t 노드는 삭제됨.(노드 갱신)
        self.size -= 1 #삭제니까 크기 감소

    def search(self, target): #target에 맞는 노드의 value 찾는 탐색 기능의 함수
        p = self.head #맨앞 헤드부터 찾는 순차탐색.순방향의 순차적 탐색만 가능. Time Complexity = O(N),N = 노드의 수
        for k in range(self.size):
            if target == p.item: #target과 노드의 value가 일치한다면,
                return k #탐색 성공
            p = p.next #다음 노드로 이동
        return None #탐색 실패
    
    def print_list(self): #노드 출력 함수
        p = self.head #맨 앞부터 시작
        while p: #노드가 존재할 때, 즉 노드가 존재하는 한 리스트의 끝까지 탐색
            if p.next != None: #다음노드가 존재할 때
                print(p.item, ' -> ', end='')
            else: #다음노드가 존재하지 않는 마지막 노드는 그냥 출력
                print(p.item)
            p = p.next #노드 순차적 탐색
        
class EmptyError(Exception): #Underflow 에러 처리
    pass
    

이 단순 연결 리스트엔 앞서 말했듯이 다양한 연산이 존재하는데,
특히 삽입 삭제 연산에 대해 구조를 알아야한다.

삽입 연산을 살펴보자면,

 def insert_front(self, item): #리스트 맨 앞에 요소 추가 O(1)
        if self.is_empty(): #빈 리스트라면?
            self.head = self.Node(item, None) #None 레퍼런스를 가진 신 노드를 헤드로 지정.
        else: #비어있지 않은 리스트라면?
            self.head = self.Node(item, self.head) #헤드 레퍼런스를 가진 노드를 헤드로 갱신
        self.size += 1 #요소 추가로 크기 증가

def insert_after(self, item, p): #특정 p가 가리키는 노드 뒤 요소 추가 O(1), 단 p가 안주어지면 O(N)- 탐색 필요
        p.next = self.Node(item, p.next) #우변 = p의 다음 레퍼런스를 가지고 있는 노드, 좌변 = p가 가르키는 노드의 다음 노드
        self.size += 1 #요소 추가로 크기 증가

아무것도 존재하지 않는 리스트라면,
링크가 없는 새 노드를 추가하면서 동시에 Head로 설정한다.
하지만, 요소가 존재하는 리스트 맨앞에 새 노드를 추가 할 때는,
추가하는 새 노드의 레퍼런스는 헤드로 갱신이 된다.

또한 특정 노드 뒤에 요소를 추가하는 함수인 insert_after() 함수는,
특정한 p가 가리키는 노드 뒤에 요소를 추가하는데.
이 과정은 예시를 통해 알아보자.

example) cherry -> pear -> apple 구조의 링크드 리스트가 존재한다면,

insert_after(mango,pear)을 실행한다.
이는,pear 뒤 mango를 가진 노드를 추가하겠다는 의미이다.
여기에서,
p 노드는 pear가 되고,
p.next는 본래 apple이 있는 자리=pear 뒤자리,
즉 mango가 들어갈 자리가 된다.
여기서 self.Node(mango,p.next) 코드,
즉 pear 뒤 자리에 들어갈 mango 노드를 생성하고
이 노드를 p.next에 연결한다.
이는 본래 apple이 있던 자리의 갱신이 이루어지며 삽입이 일어나는 것이다.

삭제 연산을 살펴보자면,

def delete_front(self): #맨 앞 노드를 삭제하는 함수 O(1)
    if self.is_empty():
        raise EmptyError('Underflow') #요소가 없는 경우 예외 처리
    else:
        self.head = self.head.next #맨 앞 노드 삭제는 단순히 헤드 노드 다음의 노드를 연결.
        self.size -= 1
    
def delete_after(self, p): #p가 가르키는 노드의 다음노드를 삭제 O(1), 단 p가 안주어지면 O(N)- 탐색 필요
    if self.is_empty():
        raise EmptyError('Underflow') #요소가 없는 경우 예외 처리
    t = p.next #t가 p가 가르키는 노드의 다음노드라 할 때,
    p.next = t.next #p가 가리키는 노드의 다음노드가 t가 가르키는 다음노드가 되도록 연결하면 p가 가르키는 다음 노드,즉 t 노드는 삭제됨.(노드 갱신)
    self.size -= 1 #삭제니까 크기 감소

맨 앞 노드를 삭제하려면,
우선 예외 처리 경우를 제외하고 맨 앞 노드 삭제는 단순히 head 다음의 노드를 head로 재지정해주면 된다.

delete_after() 함수와 같이 특정 p가 가르키는 노드의 다음 노드를 삭제하려고 하면,
일부 노드지정 및 레퍼런스 갱신이 필요하다.

example) apple -> pear -> orange 라는 링크드 리스트가 존재한다.
여기서 delete_after(apple)을 실행 했다면,
apple 노드 자체가 p가 된다.
여기서 p.next = pear 자리 = t가 되며,
p.next 노드를 t.next와 연결하면서 중간 이어진 레퍼런스를 끊어버리는 형태로 삭제연산이 이루어진다.

아래는 실행 구문 main 파일 및 실행 결과이다.

from Single_Linked_List import SList
if __name__ == '__main__': #이 파일이 메인 이라면,
    s = SList() #SLL 생성

    s.insert_front('orange') #orange 삽입
    s.insert_front('apple') #apple -> orange
    s.insert_after('cherry',s.head.next) # apple -> orange -> cherry
    s.insert_front('pear') #pear -> apple -> orange -> cherry
    s.print_list()

    print('cherry는 %d번째 입니다.' % s.search('cherry')) #cherry 는 3(idx)번째.

    print('kiwi는',s.search('kiwi')) #없는 value = None 출력

    print('pear 다음 노드 삭제 후 리스트:\t\t', end='') 
    s.delete_after(s.head) #head 다음 노드 삭제 = pear -> orange -> cherry
    s.print_list()

    print('첫 노드 삭제 후:\t\t', end='') 
    s.delete_front() #orange -> cherry
    s.print_list()

    print('첫 노드로 mango,strawberry 삽입 후:\t',end='') 
    s.insert_front('mango') #mango -> orange -> cherry
    s.insert_front('strawberry') #strawberry -> mango -> orange -> cherry
    s.print_list()

    s.delete_after(s.head.next.next) #strawberry -> mango -> orange
    print('오렌지 다음 노드 삭제 후:\t', end='')
    s.print_list()

실행 결과:

pear  -> apple  -> orange  -> cherry
cherry는 3번째 입니다.
kiwi는 None
pear 다음 노드 삭제 후 리스트:          pear  -> orange  -> cherry
첫 노드 삭제 후:                orange  -> cherry
첫 노드로 mango,strawberry 삽입 후:     strawberry  -> mango  -> orange  -> cherry
오렌지 다음 노드 삭제 후:       strawberry  -> mango  -> orange

#plus
1.삽입,삭제 연산의 시간복잡도는 O(1)인데, after() 함수 처럼 특정 노드 뒤에 요소를 삭제하려고 하는데 특정 노드가 주어지지 않는다면, O(N)의 복잡도를 가질수 있다(순차탐색 때문)

2.탐색 연산의 시간복잡도는 O(N). 이때의 N은 노드의 개수.

3.단순연결리스트(SLL)은 매우 광범위 하게 사용된다. 스택,큐,해시 테이블의 chaining,트리 등 응용범위가 넓다.

• 자료구조
• 이론