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

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

단순 연결 리스트의 개념

선형 리스트(Linear List)

• 장점
  • 배열에 구성하였기 때문에 단순하다.
  • 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다.
  • 프로그램으로 구현하기 비교적 쉽다.
• 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다.
  • 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생)

 

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

• 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다.
  • 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다.
• 데이터와 링크로 구성된 항목인 노드(Node)로 이루어진다.

노드의 구조

 

• 단순 연결 리스트에는 첫 번째 노드를 가리키는 헤드(head)를 사용한다.
  • 단순 연결 리스트가 한쪽 방향으로만 진행되어 다음 노드로 찾아갈 수 있지만, 이전 노드로는 돌아갈 수 없는데 헤드를 이용하면 처음부터 다시 진행이 가능하다.

 

노드(데이터) 삽입

• 1단계 : 삽입할 노드를 생성한다.
• 2단계 : 순서에 맞게 링크를 수정한다.
  • 새 노드의 링크에 이전 노드의 링크를 복사한다.
  • 이전 노드의 링크에 새 노드를 지정한다.

 

노드(데이터) 삭제

• 1단계 : 삭제할 노드의 바로 앞 노드 링크를 수정한다.
  • 삭제할 노드의 링크를 바로 앞 노드의 링크로 복사하여 앞 노드가 삭제할 노드의 다음 노드를 가리키게 한다.
• 2단계 : 삭제할 노드를 삭제한다.

 

단순 연결 리스트의 구현

• 헤드(head) : 첫 번째 노드를 가리킨다.
• 현재(current) : 지금 처리 중인 노드를 가리킨다.
• 이전(pre) : 현재 처리 중인 노드의 바로 앞 노드를 가리킨다.

 

• 처음에는 모두 비어 있으므면 되므로 다음과 같이 초기화한다.

memory = []
head, current, pre = None, None, None

 

① 단순 연결 리스트 생성

노드 생성

• 노드는 클래스(Class)를 사용하여 구현한다.

class Node() :
    def __init__(self):       # 생성자 함수 : 데이터형을 생성할 때 자동으로 실행
        self.data = None
        self.Link = None

• 노드 생성 및 확인

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

 

노드 연결

• 첫 번째 노드의 링크에 두 번째 노드 이름(node2)을 넣어 주면 두 노드가 단순 연결 리스트로 연결된다.

node2 = Node()
node2.data = "Banana"
node1.link = node2       # 첫 번째 노드의 링크에 두 번째 노드를 넣어 연결

 

노드 초기화

첫 번째 데이터

• 모든 노드는 head를 시작으로 연결된다.
  • 그리고 사용자가 원하는 만큼 데이터를 입력할 수 있다.

 

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

 

두 번째 이후 데이터

• 새 노드를 기준 노드의 링크에 저장하기 전에 기존 노드를 잠시 저장한 후 생성해야 한다.

 

pre = node
node = Node()
node.data = data    # 두 번째 이후 노드
pre.link = node
memory.append(node)

 

② 노드 삽입

• 노드를 단순 연결 리스트의 맨 앞, 중간, 마지막에 삽입하는 경우로 나누어 생각해 볼 수 있다.

 

첫 번째 노드 삽입

 

node = Node()
node.data = item
node.link = head
head = node

 

중간 노드 삽입

 

current = head
while 마지막 노드까지 :
    pre = current
    current = current.link
    if current.data == origin_data :
        node = Node()
        node.data = new_data
        node.link = current
    pre.link = node

 

마지막 노드 삽입

 

# 마지막 노드까지 new_data 를 찾지 못한 후
node = Node()
node.data = new_data
current.link = node

 

함수 완성

def insertNode(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

 

③ 노드 삭제

첫 번째 노드 삭제

 

current = head
head = head.link
del(current)

 

첫 번째 외 노드 삭제

 

current = head
while 마지막 노드까지 :
    pre = current
    current = current.link
    if current.data == finding_data :
        pre.link = current.link
    del(current)

 

함수 완성

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

 

④ 노드 검색

• 검색할 데이터의 노드를 반환하는 방식으로 구현해본다.

 

함수 완성

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()    # 빈 노드 반환

 

단순 연결 리스트의 완성

## 클래스와 함수 선언 부분 ##
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):
    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

# 노드 삭제 함수
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
            
# 노드 검색 함수
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)
    
    printNodes(head)

    # 삽입 예
    insertNode("다현", "화사")
    printNodes(head)

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

    insertNode("지민", "문별")    # 존재하지 않는 데이터인 지민 노드 앞에 문별 노드를 삽입한 후 출력 (맨 마지막에 삽입)
    printNodes(head)
    
    # 삭제 예
    deleteNode("다현")
    printNodes(head)

    deleteNode("쯔위")
    printNodes(head)
    
    deleteNode("지효")
    printNodes(head)
    
    deleteNode("지민")
    printNodes(head)
    
    # 검색 예
    fNode = findNode("다현")
    print(fNode.data)

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

    fNode = findNode("지민")
    print(fNode.data)

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

 

 

(참고) 이중 연결 리스트(Doubly Linked List)

개념

• 양방향으로 링크가 연결되어 노드의 양방향으로 접근하기가 용이한 리스트

 

구현

노드

• 2개의 링크와 1개의 데이터가 한 노드로 구성된다.
  • 앞의 노드를 가리크는 링크 : plink
  • 다음 노드를 가리키는 링크 : nlink

class Node2() :
    def __init__ (self) :
        self.plink = None		# 앞쪽 링크
        self.data = None
        self.nlink = None		# 뒤쪽 링크

 

코드

• 단순 연결 리스트를 구현했던 코드에서 노드를 약간 수정하여 이중 연결 리스트처럼 출력해본다.

## 클래스와 함수 선언 부분 ##
class Node2() :
    def __init__ (self) :
        self.plink = None		# 앞쪽 링크
        self.data = None
        self.nlink = None		# 뒤쪽 링크

def printNodes(start):
    current = start
    if current.nlink == None :
        return
    print("정방향 --> ", end=' ')
    print(current.data, end=' ')
    while current.nlink != None:
        current = current.nlink
        print(current.data, end=' ')
    print()
    print("역방향 --> ", end=' ')
    print(current.data, end=' ')
    while current.plink != None:
        current = current.plink
        print(current.data, end=' ')

## 전역 변수 선언 부분 ##
memory = []
head, current, pre = None, None, None
dataArray = ["다현", "정연", "쯔위", "사나", "지효"]

## 메인 코드 부분 ##
if __name__ == "__main__" :
    node = Node2()			# 첫 번째 노드
    node.data = dataArray[0]
    head = node
    memory.append(node)

    for data in dataArray[1:] :		# 두 번째 이후 노드
        pre = node
        node = Node2()
        node.data = data
        pre.nlink = node
        node.plink = pre
        memory.append(node)

    printNodes(head)

정방향 -->  다현 정연 쯔위 사나 지효 
역방향 -->  지효 사나 쯔위 정연 다현