단순 연결 리스트의 일반 구현과 응용

 1  단순 연결 리스트의 생성

단순 연결 리스트의 간단 구현에선 데이터를 5개로 제한했지만 데이터 개수가 제한적이지 않을 때가 일반적이다.

사용자가 입력하거나 배열에서 데이터를 추출한 후 값을 계속 단순 연결 리스트로 만드는 코드를 작성한다.

그러려면 첫 번째 데이터는 빈 노드를 생성하고 사용자가 키보드로 첫 번째 데이터를 입력하거나 데이터 저장소에서 데이터를 가져와서 대입해야 한다. 두 번째 이후 데이터는 새 노드를 기존 노드의 링크에 저장하기 전에 기존 노드를 잠시 저장한 후 생성해야 한다. 변수 이름을 여러 개 사용하지 않아도 되며, 모든 노드는 head를 시작으로 연결된다.

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

이렇게 단순 연결 리스트를 생성하는 함수를 만들었다.

 

 2  노드 삽입

위에서 완성된 연결 리스트에 노드를 삽입하는 방식을 만든다. 

노드를 맨 앞에 삽입하는 과정은 노드를 생성하고, 링크한뒤, head 노드를 바꾼다.

중간에 삽입하는 과정은 head에서 시작하여 현재(current) 노드를 확인한다. 현재 노드를 이전(pre) 노드로 저장하고, 다음 노드로 이동한다. 삽입할 전 노드가 나오기 전까지 과정을 반복한 뒤 삽입해야 할 위치를 찾으면 새 노드의 링크를 연결한다. 이전 노드의 링크를 새 노드로 지정한다.

마지막 노드를 삽입하는 과정의 앞부분은 중간과 같다. 마지막에 새 노드를 생성한 뒤 현재 노드의 링크를 새 노드로 지정한다.

## 클래스와 함수 선언 부분 ##
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
        haed = 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)     
    
    insertNode("다현", "화사")
    printNodes(head)
    
    insertNode("사나", "솔라")
    printNodes(head)
    
    insertNode("재남", "문별")
    printNodes(head)

 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)

 

 

위에 코드에서 노드가 삭제될 때마다 어디에 노드가 삭제됐는지 알려주는 기능을 추가해보자.

## SELF STUDY ##
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
    
    fNode = findNode(deleteData)
    if fNode.data == None :
        print("#삭제된 노드가 없음 #")
    else :
        if dataArray[0] == deleteData :
            print(" # 첫 노드가 삭제 됨 #")
        elif dataArray[-1] == deleteData :
            print(" # 마지막 노드가 삭제 됨 #")
        else :
            print(" # 중간 노드 삭제 됨 #")
    
    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)
    
    deleteNode("다현")
    printNodes(head)
    
    deleteNode("쯔위")
    printNodes(head)

    deleteNode("사나")
    printNodes(head)
    
    deleteNode("재남")
    printNodes(head)

 

 4  노드 검색

완성된 단순 연결 리스트에서 노드를 검색하는 방식을 구현해 보자.

현재 노드를 첫 번째 노드인 헤드와 동일하게 만들고, 현재 노드가 검색할 데이터인지 비교한다.

현재 노드를 다음 노드로 이동하고, 검색할 데이터와 동일하면 현재 노드를 반환한다. 

## 클래스와 함수 선언 부분 ##
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 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)
    
    fNode = findNode("다현")
    print(fNode.data)
    
    fNode = findNode("쯔위")
    print(fNode.data)

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

 

 5  단순 연결 리스트의 응용

단순 연결 리스트를 응용하여 간단한 [명함관리] 프로그램을 만든다.

이름과 연락처를 무작위로 입력하면 이름 순서대로 단순 연결 리스트에 저장한다.

일반 구현에서 사용했던 방식을 응용한다. 리스트는 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 makeSimpleLinkedList(namePhone) :
    global memory, head, current, pre
    printNodes(head)
    
    node = Node()
    node.data = namePhone
    memory.append(node)
    if head == None :
        head = node
        return
    
    if head.data[0] > namePhone[0] :
        node.link = head
        head = node
        return
    
    current = head
    while current.link != None :
        pre = current
        current = current.link
        if current.data[0] > namePhone[0] :
                pre.link = node
                node.link = current
                return
            
    current.link = node
    
memory = []
head, current, pre = None, None, None
dataArray = [['지민', '010-1111-1111'], ['정국', '010-2222-2222'], ['뷔', '010-3333-3333'], ['슈가', '010-4444-4444'], ['진', '010-5555-5555'],]

if __name__ == "__main__" :
    
    for data in dataArray :
        makeSimpleLinkedList(data)
        
    printNodes(head)

 

이번엔 dataArray에 키를 사용해서 키 순서대로 단순 연결 리스트를 생성한다.

dataArray = [["지민", "180"], ["정국", "177"], ["뷔", "183"], ["슈가", "175"], ["진", "179"]]

## SELF STUDY ##
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 makeList(namelength):
    global memory, head, current, pre
    printNodes(head)

    node = Node()
    node.data = namelength
    memory.append(node)

    if head == None:        #첫 번째 노드일 때
        head = node
        return
        # 첫 번째 노드보다 작을 때
    if head.data[1] > namelength[1]:
        node.link = head
        head = node
        return

        # 중간 노드로 삽입하는 경우
    current = head
    while current.link != None:
        pre = current
        current = current.link
        if current.data[1] > namelength[1]:
            pre.link = node
            node.link = current
            return

    # 삽입하는 노드가 가장 큰 경우
    current.link = node


## 전역 변수 선언 부분 ##
memory = []
head, current, pre = None, None, None
codeArray = [["지민", "180"], ["정국", "177"], ["뷔", "183"], ["슈가", "175"], ["진", "179"]]

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

    for data in codeArray:
        makeList(data)

    printNodes(head)