[Section 2] 단 방향 연결 리스트(Singly Linked Lists)

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

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

0. INTRO

단 방향 연결 리스트는 한쪽 방향으로 만 연결된 자료 구조를 의미한다. 연결 리스트의 가장 기본적 형태인 단방향 리스트를 이해하고 구현해보자. 

1. 단 방향 연결 리스트의 구조와 기능

단 방향 연결 리스트 자료 구조의 개요도는 다음과 같다. 데이터 1의 앞부분을 헤드(head)라고 부른다. 따라서 각 데이터 블록의 널 포인트를 기점으로 연결되어 있는 것을 확인할 수 있다. 

단 방향 연결리스트 개요도

 

단 방향 연결 리스트를 구현하기 위해 ADT에 대해 알아보도록 하자. 가장 먼저 자료들의 탐색이 가능해야 한다. 그리고 자료 구조에 새로운 항목을 추가할 수 있어야 하고, 특정 항목을 제거할 수 있어야 한다. 각각의 기능을 코드로 구현해보고 확인해보자.

 

* 간단함을 위해 정수 형태의 데이터로 리스트를 구현하고자 한다. 아래의 내용은 클래스의 방법과 속성에 대한 이해를 전제하여 서술하고 있다.

 

 노드 클래스 생성하기

다음과 같은 예시 코드로 단 방향 연결 리스트를 위한 노드 클래스를 생성해보자.

 

예시 코드:

class Node:

    def __init__(self,data = None, node=None):

        self.data=data

        self.node=node

    def setD(self,data):
        self.data=data
    def setN(self,node):
        self.node=node

 

코드 결과:

노드 생성 클래스 생성 예시

2. 연결 리스트의 연결 개념 이해하기

연결리스트의 연결 개념을 위해서 다음의 프로그램 동작 결과를 확인해보자.

 

코드 결과:

연결리스트의 연결 동작 이해하기

 

데이터의 삽입을 직접 입력하여 동작한 코드이다. 위 연결 리스트에는 헤드(head)포인터가 존재하지 않는데, 이를 구현하고 삽입과 삭제 기능을 추가한다면, 조금 더 완벽한 연결리스트가 될 수 있을 것이다.