[Python] 파이썬 기초 19/20, 단순연결리스트 생성 삽입 삭제 스택

<내용정리>

- 관련 파일

단순연결리스트.py

0.00MB

단순연결리스트02_일반버전.py

0.00MB

단순연결리스트03_일반버전_삽입.py

0.00MB

단순연결리스트04_일반버전_삭제.py

0.00MB

스택01_일반버전.py

0.00MB

 

- 본문

1) 단순연결 리스트

### 데이터가 5개인 단순연결리스트 생성
## 노드(Node) 클래스 정의
class Node:
    def __init__(self):
        self.data = None
        self.link = None

node1 = Node()
node1.data = '다현'
node2 = Node()
node2.data = '정연'
node1.link = node2

node3 = Node()
node3.data = '쯔위'
node2.link = node3

node4 = Node()
node4.data = '사나'
node3.link = node4

node5 = Node()
node5.data = '지효'
node4.link = node5

current = node1
print(current.data, end='->')
while current.link != None:
    current = current.link  # 다음 노드를 현재 노드로 지정
    print(current.data, end='->')

 

2) 단순연결리스트 - 생성

### 단순연결리스트 생성 : 일반버전
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

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()

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)

 

3) 단순연결리스트 - 삽입

### 단순연결리스트 삽입 : 일반버전
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

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 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

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)

 

4) 단순연결리스트 - 삭제

### 단순연결리스트 삭제 : 일반버전
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

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 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

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('재남')  # 존재하지 않는 노드 삭제 : 변화 X
    printNodes(head)

 

5) 단순연결리스트 - 스택

### 스택 동작을 위한 일반 코드
SIZE = int(input('스택 크기를 입력하세요 --> '))
stack = [None for _ in range(SIZE)]  # 리스트 내포
top = -1

def isStackFull():
    """ 스택이 꽉 찼는지 확인하는 함수 """
    if top == SIZE-1:  # 스택이 꽉 찬 상태
        return True
    else:
        return False

def isStackEmpty():
    """ 스택이 비었는지 확인하는 함수 """
    if top == -1:  # 스택이 빈 경우
        return True
    else:
        return False

def push(data):
    """ 스택에 데이터를 삽입하는 함수 """
    global stack, top
    if isStackFull():
        print('스택이 꽉 찼습니다')
        return
    top += 1
    stack[top] = data

def pop():
    """ 스택에서 데이터를 추출하는 함수 """
    global stack, top
    if isStackEmpty():
        print('스택이 비었습니다')
        return None
    data = stack[top]  # 데이터 추출
    stack[top] = None  # 그 자리에 None을 대입하여 삭제
    top -= 1
    return data  # 추출한 데이터 반환

def peek():
    """ 스택에서 top 위치의 데이터를 확인하는 함수 """
    if isStackEmpty():
        return None
    return stack[top]  # 현재 top 위치의 데이터를 반환

## 메인 코드 부분
if __name__ == '__main__':
    while True:
        select = input('삽입(I) / 추출(E) / 확인(V) / 종료(X) 중 하나를 선택 --> ')
        if select == 'i' or select == 'I':
            data = input('입력할 데이터 --> ')
            push(data)  # 삽입 함수 호출
            print('스택상태 --> ', stack)
        elif select == 'e' or select == 'E':
            data = pop()  # 추출 함수 호출
            print('추출된 데이터 --> ', data)
            print('스택상태 --> ', stack)
        elif select == 'v' or select == 'V':
            data = peek()  # 확인 함수 호출
            print('확인된 데이터 --> ', data)
            print('스택상태 --> ', stack)
        elif select == 'x' or select == 'X':
            print('프로그램 종료')
            break
        else:
            print('입력이 잘못되었습니다')