[Linked Lists]3. 단일 연결 리스트 구현

목차

1. Singly LInked LIst에 필요한 함수 목록

2. class Node

3. Empty()

4. LIst_size()

5. Print()

6. Append(data)

7. Delete(idx)

8. Insert(idx, data)

9. 테스트

1. Singly Linked List에 필요한 함수 목록

 위의 목차에서 추측할 수 있는 내용이지만, Singly LInked List에 필요한 함수의 목록으로는

1. Empty() : 연결 리스트가 비어있는지 확인하는 함수

2. List_size(): 연결 리스트의 크기를 확인하는 함수

3. Print(): 연결리스트에 포함되어 있는 모든 data를 출력하는 함수

4. Append(data): 연결리스트에 data를 추가하는 함수

5. Delete(idx): 연결리스트의 인덱스 idx에 해당하는 값을 삭제하는 함수

6. Insert(idx, data): 연결리스트의 인덱스 idx에 data를 추가하는 함수

 

2. class Node

class Node: # class Node
    def __init__(self, data: int):
        self.data = data # 저장하는 데이터 값
        self.next = None # 다음 node의 주소값 저장

 

3. Empty()

def empty(self)-> int: # 리스트가 비어있는지 확인하는 함수
    if self.head == None and self.tail == None:
        return 1 # 비어있다면 1 return
    else:
        return 0 # 비어있지 않다면 0 return

 

4. List_size()

def list_size(self)-> int: # 리스트의 크기를 반환하는 함수
    list_size = 1
    our_node = self.head # head에서 시작
    
    if self.empty(): # 비어있다면 0 return
        return 0
    else:
        while True:
            if our_node.next == None: # 다음 node가 없다면
                break
            else: # 다음 node가 있다면
                list_size += 1
                our_node = our_node.next
        return list_size

 

5. Print()

def print(self)-> str: # 연결 리스트의 elements를 출력하는 함수
    our_node = self.head
    tmp = ''
    
    if self.empty(): # 리스트가 비어있다면 -1 return
        return '-1'
    else:
        while True:
            tmp += str(our_node.data) + ' '
            if our_node.next == None:
                break
            else:
                our_node = our_node.next
        return tmp

 

6. Append(data)

def append(self, data: int): # 연결 리스트에 node를 추가하는 함수
    node = Node(data)
        
    if self.empty(): # 리스트가 비어있다면, head와 tail 지정해주기
        self.head = node
        self.tail = node
    else: # tail이 가리키는 node 변경 후 tail 변경
        self.tail.next = node
        self.tail = node

 

7. Delete(idx)

def delete(self, idx: int)-> int: # idx에 해당하는 node를 삭제하고, 그 node의 data 출력
    location = 0 # 현재 위치
    cur_node = self.head
    pre_node = None
        
    if self.empty() or self.list_size() < idx: # 연결 리스트가 비어있거나, 벗어나는 값을 받은 경우
        return -1
    elif idx == 0: # 0번째 idx를 삭제하는 경우(head)
        tmp = self.head.data
        self.head = self.head.next
        return tmp
    else: # pre_node와 cur_node로 해당하는 idx의 node를 제거
        while True:
            if location == idx:
                tmp = cur_node.data
                pre_node.next = cur_node.next
                break
            else:
                pre_node = cur_node
                cur_node = cur_node.next
                location += 1
        return tmp

 

8. Insert(idx, data)

def insert(self, idx: int, data: int): # idx 위치에 data를 가지는 node 삽입하는 함수
    node = Node(data) # 새로운 노드
    location = 0 # 현재 위치
    cur_node = self.head
    pre_node = None
        
    if idx == 0: # idx가 0인 경우, 연결 리스트 가장 앞에 삽입
        if self.empty(): # 리스트가 비어있는 경우
            self.head = node
            self.tail = node
        else: # 리스트가 비어있지 않다면, 맨 앞에 삽입
            node.next = self.head
            self.head = node
    elif idx < 0 or idx > self.list_size(): # idx가 0보다 작거나, 리스트 크기보다 큰 경우
        return
    elif idx == self.list_size()-1: # idx가 리스트의 마지막 index인 경우
        self.append(data)
    else:
        while True:
            if location == idx:
                node.next = cur_node
                pre_node.next = node
                break
            else:
                pre_node = cur_node
                cur_node = cur_node.next
                location += 1

 

9. 테스트

if __name__ == "__main__": # 테스트 해보기
    s_list = S_linked_list()
    print('made s_list')
    print(f's_list.empty(): {s_list.empty()}')
    print(f's_list.list_size(): {s_list.list_size()}')
    print(f's_list.print(): {s_list.print()}')
    print()
    
    s_list.append(1)
    print('append 1')
    print(f's_list.empty(): {s_list.empty()}')
    print(f's_list.list_size(): {s_list.list_size()}')
    print(f's_list.print(): {s_list.print()}')
    print()
    
    s_list.append(2)
    s_list.append(3)
    s_list.append(4)
    print('append 2, 3, 4')
    print(f's_list.empty(): {s_list.empty()}')
    print(f's_list.list_size(): {s_list.list_size()}')
    print(f's_list.print(): {s_list.print()}')
    print()
    
    print('delete 3')
    print(f's_list.delete(3):{s_list.delete(3)}')
    print(f's_list.empty(): {s_list.empty()}')
    print(f's_list.list_size(): {s_list.list_size()}')
    print(f's_list.print(): {s_list.print()}')
    print()
    
    s_list.insert(1, 10)
    print('insert data:10 in idx:1')
    print(f's_list.empty(): {s_list.empty()}')
    print(f's_list.list_size(): {s_list.list_size()}')
    print(f's_list.print(): {s_list.print()}')
    print()

 

출력 값:

made s_list
s_list.empty(): 1
s_list.list_size(): 0
s_list.print(): -1

append 1
s_list.empty(): 0
s_list.list_size(): 1
s_list.print(): 1

append 2, 3, 4
s_list.empty(): 0
s_list.list_size(): 4
s_list.print(): 1 2 3 4

delete 3
s_list.delete(3):4
s_list.empty(): 0
s_list.list_size(): 3
s_list.print(): 1 2 3

insert data:10 in idx:1
s_list.empty(): 0
s_list.list_size(): 4
s_list.print(): 1 10 2 3

 

전체 코드는 github에 올려두었습니다.

github.com/imgzon3/algorithm/blob/main/Linked_LIst/singly_linked_list.py

imgzon3/algorithm