[자료구조] 단순 연결 리스트(Singly Linked List)

📌 현재 게시글의 개념과 코드는 이 책을 참고하여 정리하였습니다.

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

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

단순 연결 리스트(Singly Linked List)는 데이터를 노드 단위로 삽입/삭제한다.

• 물리적으로 연결되어 있지 않은 데이터가 연결된다.
• 연결을 위한 Link가 필요하다.
• 노드(Node)를 사용해서 데이터를 표현한다.

단순 연결 리스트의 원리

리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료 구조이다.

배열의 순서는 실제와 같은 물리적인 반면, 리스트의 순서는 논리적이라 볼 수 있다.

배열을 이용해 리스트를 구현하면 논리적 순서를 지키기 위해 원소의 이동이 불가피하다.

또한 순서대로 저장되기 때문에 데이터만 있으면 된다.

반면 단순 연결 리스트는 일반적으로 포인터 변수를 이용한 연결 리스트를 이용한다. 이 책에서는 링크라고 표현한다.

포인터 변수라는 것은 다음 원소를 가리키는 위치를 저장하는 곳이다.

배열은 아래의 그림과 같이 생겼다.

선형 리스트에 대한 설명은 이 글을 참고하면 도움이 될 듯 하다.

노드의 구조는 이렇다.

데이터와 링크가 함께 구성된 항목을 노드(Node)라고 한다.

• 노드: 데이터와 링크가 함께 구성된 항목
• 헤드: 첫 번째 노드
• 링크: 다음 데이터를 가리키는 포인터 변수

이렇게 크게 3가지의 용어를 정리하고 넘어가겠다.

단순 연결 리스트 간단 구현

(1) 노드 생성과 연결

## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):                  # 매개변수로 시작 노드를 전달 받음
    current = start                     # 전달 받은 시작 노드를 현재 노드로 지정
    if current == None:                 # 노드에 데이터가 하나도 없는 연결 리스트인 경우 반환
        return
    print(current.data, end=' ')        # 현재 노드 출력
    while current.link != None:         # 노드의 링크가 빌 때까지 출력
        current = current.link
        print(current.data, end=' ')
    print()
    
## 전역 변수 선언 부분 ##
memory = []                             # 생성할 노드 저장할 메모리 준비
head, current, pre = None, None, None   # 시작 노드, 현재 노드, 이전 노드에 사용할 변수 준비
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.link = node                 # 이전 노드 링크에 새 노드 대입
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNodes(head)                    # 생성이 완료된 단순 연결 리스트 출력

Out:

다현 정연 쯔위 사나 지효

1. class를 이용해서 빈 노드를 만든다.
2. printNodes 현재 노드를 출력해주는 함수를 만든다.
3. 전역 변수 선언
4. 노드를 계속 생성하여 단순 연결 리스트를 완성한다.

(2) 노드 삽입 함수

## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):                  # 매개변수로 시작 노드를 전달 받음
    current = start                     # 전달 받은 시작 노드를 현재 노드로 지정
    if current == None:                 # 노드에 데이터가 하나도 없는 연결 리스트인 경우 반환
        return
    print(current.data, end=' ')        # 현재 노드 출력
    while current.link != None:         # 노드의 링크가 빌 때까지 출력
        current = current.link
        print(current.data, end=' ')
    print()

def insertNode(findData, insertData):   # 매개 변수로 삽입할 위치를 찾을 데이터(findData), 삽입할 데이터(insertData)를 넘겨 받는다.
    global memory, head, current, pre

    if head.data == findData :          # 첫 번째 노드 삽입
        node = Node()
        node.data = insertData
        node.link = head
        head = node
        return

    current = head
    while current.link != None :        # 중간 노드 삽입
        pre = current
        current = current.link
        if current.data == findData:
            node = Node()
            node.data = insertData
            node.link = current
            pre.link = node
            return
    
    node = Node()                       # 마지막 노드 삽입
    node.data = insertData
    current.link = node


## 전역 변수 선언 부분 ##
memory = []                             # 생성할 노드 저장할 메모리 준비
head, current, pre = None, None, None   # 시작 노드, 현재 노드, 이전 노드에 사용할 변수 준비
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드 선언 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.link = node                 # 이전 노드 링크에 새 노드 대입
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNodes(head)                    # 생성이 완료된 단순 연결 리스트 출력

    insertNode("다현", "화사")
    printNodes(head)

    insertNode("사나", "솔라")
    printNodes(head)

    insertNode("재남", "문별")
    printNodes(head)

Out:

다현 정연 쯔위 사나 지효 
화사 다현 정연 쯔위 사나 지효 
화사 다현 정연 쯔위 솔라 사나 지효
화사 다현 정연 쯔위 솔라 사나 지효 문별

해당 코드는 insertNode 함수를 만들어서 데이터를 삽입하는 과정이다.

(3) 노드 삭제 함수

## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):                  # 매개변수로 시작 노드를 전달 받음
    current = start                     # 전달 받은 시작 노드를 현재 노드로 지정
    if current == None:                 # 노드에 데이터가 하나도 없는 연결 리스트인 경우 반환
        return
    print(current.data, end=' ')        # 현재 노드 출력
    while current.link != None:         # 노드의 링크가 빌 때까지 출력
        current = current.link
        print(current.data, end=' ')
    print()

def deleteNode(deleteData):
    global memory, head, current, pre

    if head.data == deleteData:         # 첫 번째 노드 삭제
        current = head
        head = head.link
        del(current)
        return

    current = head                      # 첫 번째 외 노드 삭제
    while current.link != None:
        pre = current
        current = current.link
        if current.data == deleteData:
            pre.link = current.link
            del(current)
            return


## 전역 변수 선언 부분 ##
memory = []                             # 생성할 노드 저장할 메모리 준비
head, current, pre = None, None, None   # 시작 노드, 현재 노드, 이전 노드에 사용할 변수 준비
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드 선언 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.link = node                 # 이전 노드 링크에 새 노드 대입
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNodes(head)                    # 생성이 완료된 단순 연결 리스트 출력

    deleteNode("다현")
    printNodes(head)

    deleteNode("쯔위")
    printNodes(head)

    deleteNode("지효")
    printNodes(head)

    deleteNode("재남")
    printNodes(head)

Out:

다현 정연 쯔위 사나 지효 
정연 쯔위 사나 지효 
정연 사나 지효
정연 사나
정연 사나

위 코드는 deleteNode 함수를 만들어서 데이터를 삭제해준다.

(4) 노드 검색 함수

## 클래스와 함수 선언 부분 ##
class Node():
    def __init__ (self):
        self.data = None
        self.link = None

def printNode(start):
    current = start
    if current == None:
        return
    print(current.data, end=' ')
    while current.link != None:
        current = current.link
        print(current.data, end=' ')
    print()

def findNode(findData):
    global memory, head, current, pre

    current = head
    if current.data == findData:
        return current
    while current.link != None:
        current = current.link
        if current.data == findData:
            return current
    return Node()       # 빈 노드 반환


## 전역 변수 선언 부분 ##
memory = []                             # 생성할 노드 저장할 메모리 준비
head, current, pre = None, None, None   # 시작 노드, 현재 노드, 이전 노드에 사용할 변수 준비
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드 선언 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.link = node                 # 이전 노드 링크에 새 노드 대입
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNode(head)                    # 생성이 완료된 단순 연결 리스트 출력

    fNode = findNode("다현")
    print(fNode.data)

    fNode = findNode("쯔위")
    print(fNode.data)

    fNode = findNode("재남")
    print(fNode.data)

Out:

다현 정연 쯔위 사나 지효 
다현
쯔위
None

findNode를 통해 노드 안에 데이터가 있는지 알려주고, 데이터가 존재하지 않으면 None을 return한다.

Reference

🔗 [자료구조] 단순 연결 리스트(singly linked list) - 정리 및 연습문제