단순 연결 리스트

개념

1) 선형 리스트: 배열에 데이터를 차례대로 저장, 데이터의 실제 위치 순서로 구성
--> 장점: 데이터 찾기, 구현 용이
     단점: 데이터 삽입, 삭제 작업 시 오버헤드 발생
2) 단순 연결 리스트: 저장된 노드들이 물리적으로 떨어진 곳에 위치, 순차적 x

원리

노드 구조

1) 선형 리스트: 노드에 데이터 (값)만 존재
2) 단순 연결 리스트: 노드에 데이터 (값), 링크 존재
  * head: 첫 번째 노드
--> 단순 연결 리스트는 다음 노드로는 이동 가능하지만, 이전 노드로는 이동이 불가능한데, head를 이용하여 이전 노드로 이동 가능 (첫 노드부터 재시작)

노드 삽입

* 새 노드 생성 -> 링크 수정

노드 삭제

* 링크 수정 -> 노드 삭제

간단 구현

노드 생성, 연결

--> 노드 생성은 클래스를 사용하여 구현

노드 생성

class Node():
    def __init__(self):
        self.data = None # 데이터 생성
        self.link = None # 링크 생성
node1 = Node() # 빈 노드 생성
node1.data = '다현' # 데이터 추가

노드 연결

node2 = Node() # 두 번째 빈 노드 생성
node2.data = '정연'
node1.link = node2 # 첫 번째 노드의 링크에 두 번째 노드를 연결

데이터가 5개인 단순 연결 리스트 생성

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: 현재 노드 위치, 1씩 증가시켜 리스트 출력이 가능하다.

current = node1
print(current.data, end = ' ')
while current.link != None: # 마지막 데이터까지 반복
    current = current.link # 다음 노드로 이동
    print(current.data, end = ' ')

노드 삽입

새 노드 생성 -> 데이터 입력 -> 이전 노드의 링크 복사 -> 이전 노드의 링크 삽입 노드로 변경

newNode = Node()
newNode.data = '재남'
newNode.link = node2.link
node2.link = newNode

노드 삭제

삭제할 노드 링크를 바로 앞 노드의 링크로 복사 -> 노드 삭제

node2.link = node3.link
del(node3)

일반 구현

단순 연결 리스트의 일반 형태

memory = []
head, current, pre = None, None, None
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)

노드 삽입

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