단일 연결 리스트 - python3

연결 리스트(Linked List) 란

• 연결 리스트 == 링크드 리스트
• 각 노드가 데이터와 포인터를 가지고 연결되어 있는 구조

연결 리스트

연결 리스트 

• 연길 리스트에서는 노드와 포인터가 있다.
  • 노드 : 데이터의 값과,포인터로 구성되어 있음
  • 포인터 : 각각의 노드 안에서 다음 노드로 가거나 이전 노드와의 연결 정보를 가지고 있음

연결 리스트 특징

• 배열과는 다르게 크기가 고정되어 있지 않아 삽입/삭제가 용이하다.
• 탐색시 모든 노드를 처음부터 탐색하기 때문에 탐색시간이 길어질 수 있다.
• 데이터의 추가 삭제가 많을 경우에는 연결 리스트를 사용하는게 유리하고, 검색/정렬을 자주할 땐 배열이 유리하다.
• 중간 데이터를 삭제시에, 삭제한 노드의 전 노드와 앞 노드를 다시 연결해줘야하는 과정이 필요

연결 리스트 종류

• 단일 연결 리스트 : 각 노드에 데이터 | 포인터 => 로 한 개의 포인터가 다음 노드를 가리킨다.

• 이중 연결 리스트 : 각 노드에 포인터 | 데이터 | 포인터 => 로 두 개의 포인터가 각각 이전 노드와 다음 노드를 가리킨다.

• 원형 연결 리스트 : 각 노드에 데이터 | 포인터 => 로 마지막 노드와 처음 노드를 가리킨다.

단일 연결 리스트 실습 - python

# 노드 클래스 작성
class Node:
    def __init__(self, data, next=None):
        self.data=data
        self.next=next

# 노드에 데이터를 추가할 함수 작성
def add(data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data)
    
# 노드 연결
nodeStart = Node("head시작")
head = nodeStart
# 노드에 1~9까지 데이터를 순서대로 넣음 
for data in range(1,10):
    add(data)
    
    
node = head # 연결된 노드들을 출력하기에 앞서 처음 시작한 head부분을 알아야 검색 가능
while node.next: # 노드에 포인터가 가리키는게 없을때까지 반복
    print(node.data)
    node = node.next
print(node.data)

결과

 

 

 

 

 

 

---

단일 연결 리스트 실습 응용

• 단일 연결 리스트는 데이터의 탐색을 위해 첫 노드부터 끝까지 탐색을 하게되는 특징을 이용해 각자 다른 두 개의 head 노드를 생성하고 데이터를 삽입하여 각각의 head 노드 가리킬 때 어떤 값을 출력하나 확인함

# 노드 클래스 작성
class Node:
    def __init__(self, data, next=None):
        self.data=data
        self.next=next

# 노드에 데이터를 추가할 함수 작성
def add(head,data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data)

# 노드 연결 - test node 1
nodeHead1 = Node("head시작 1")
head1 = nodeHead1
# 노드에 1~9까지 데이터를 순서대로 넣음
for data in range(1,10):
    add(head1,data)
    
# 노드 연결 - test node 2
nodeHead2 = Node("head시작 2")
head2 = nodeHead2

for data in range(10,20):
    add(head2,data)
    
node = nodeHead1  # test node 1 연결 및 출력
while node.next:
    print(node.data)
    node = node.next
print(node.data)
print("---------------------------------------------------------------------")

node = nodeHead2  # test node 2 연결 및 출력
while node.next: 
    print(node.data)
    node = node.next
print(node.data)
print("---------------------------------------------------------------------")

node = nodeHead1  # test node 1 연결 및 출력
while node.next: 
    print(node.data)
    node = node.next
print(node.data)

결과

 

단일 연결 리스트 실습 응용 - 중간 노드 연결

# 노드 클래스 작성
class Node:
    def __init__(self, data, next=None):
        self.data=data
        self.next=next

# 노드에 데이터를 추가할 함수 작성
def add(head,data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data)
    
# 노드 연결 - test node 1
nodeHead1 = Node("head시작 1")
head1 = nodeHead1
# 노드에 1~9까지 데이터를 순서대로 넣음 2부터 시작하는 이유는 head부분에 이미 1을 넣어놨기 때문에 2부터
for data in range(1,10):
    add(head1,data)
    
    
# 중간에 추가할 노드 생성
newNode = Node(1.5)

node = head1

while True:
    # 현재 1과 2사이에 넣기 위해서 1이 들어있는 node를 찾아야함
    if node.data == 1:
        break
    else:
        node = node.next
# 임시 변수에 찾은 node의 다음 포인터를 저장 * tmp에는 2가 들어있는 node를 가리키는 포인터를 가지고 있음
tmp = node.next
# 1번 포인터가 새로 생성한 노드인 newNode를 가리킴
node.next = newNode
# 새로 생성한 newNode 포인터가 2가 들어있는 포인터를 가리킴
newNode.next = tmp


node = head1  # test node 1 연결 및 출력
while node.next:
    print(node.data)
    node = node.next
print(node.data)

결과

 

단일 연결 리스트 실습 응용 - 노드 추가

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class NodeModule:
    # 생성자로 NodeModule 생성시 head값을 초기화
    def __init__(self, data):
        self.head = Node(data)
        self.list_size = 1
        print("생성자실행")
        
    # 노드 추가하는 함수    
    def add(self, data):
        if self.head == None:
            self.head = Node(data)
            # 처음 생성한 node의 head가 none일 경우 첫 node data를 삽입하고 list size +1
            self.list_size += 1
        else:
            node=self.head
            while node.next:
                node=node.next
            node.next = Node(data)
            self.list_size += 1
           
    # 노드를 보여주는 함수
    def show(self):
        node = self.head
        while node.next:
            print(node.data)
            node = node.next
        print(node.data)

 

단일 연결 리스트 실습 응용 - 노드 삭제 ( head 노드, 중간 노드, 마지막 노드 )

• 연결리스트의 삭제
  • head를 삭제하는 경우, 그 다음 노드를 head노드로 바꿔줘야함
  • 중간 노드를 삭제하는 경우, 이전 노드와 그 다음 노드를 다시 이어줘야함
  • 마지막 노드를 삭제하는 경우, 삭제하고 그 이전노드의 포인터를 None이나 null로 선언해줘야한다.

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class NodeModule:
    # 생성자로 NodeModule 생성시 head값을 초기화
    def __init__(self, data):
        self.head = Node(data)
        self.list_size = 1

    # 노드를 보여주는 함수
    def show(self):
        node = self.head
        while node.next:
            print(node.data)
            node = node.next
        print(node.data)
            
    # 노드를 삭제하는 함수
    def deleteNode(self, num):
        # head가 없을 경우
        if(self.head == None):
            print("Node의 head가 존재하지 않음")
            return
        
        # head node를 삭제하는 경우
        if self.head.data == num:
            # 임시변수에 현재 node head를 저장
            tmp = self.head
            # 현재 노드의 head를 삭제할 head node의 다음 node로 
            self.head = self.head.next
            # 기존의 head노드를 삭제
            del tmp
        # 중간 노드와 마지마 노드 삭제하는 코드
        else:
            node=self.head
            isData = False
            # 입력한 데이터가 노드에 존재하는 데이터인지 확인
            while node.next:
                if node.next.data == num:
                    isData = True
                node = node.next
                
            if isData == True:
                node = self.head
                while node.next:
                    if node.next.data == num:
                        tmp = node.next
                        # 만약 node.next가 마지막 노드라면 node.next.next는 None이기 때문에
                        # 중간노드일 경우와 마지막 노드일 경우 모두 해결할 수 있음
                        node.next = node.next.next
                        del tmp
                        return
                    node=node.next
            else:
                print("입력한 데이터가 노드에 존재하지 않습니다.")
                return