자료구조01. 리스트 list

자료구조01. 리스트 list

단순 연결 리스트

- 노드들이 물리적으로 떨어진 곳에 위치함

- 각 노드(데이터와 링크로 구성된 항목)의 번지도 순차적이지 않음

- 링크를 따라가면 선형 리스트 순서와 같음

# 1. 노드 생성 class Node() : def __init__ (self) : self.data = None self.link = None # 첫 번째 노드 생성 node1 = Node() node1.data = "다현" print(node1.data, end=' ') # 2. 노드 연결 : 두 번째 노드를 생성하고 첫 번째 노드와 연결 node2 = Node() node2.data = "정연" node1.link = node2 # 첫 번째 노드의 링크에 두 번째 노드를 넣어 연결 node3 = Node() node3.data = "쯔위" node2.link = node3 node4 = Node() node4.data = "사나" node3.link = node4

단순 연결 리스트 간단하게 구현하기

1. 첫 번째 노드를 현재(current) 노드로 지정하고, 현재 노드의 데이터인 다현을 출력

2. 현재 노드의 링크가 비어있지 않다면 현재 노드를 현재 노드의 링크가 가리키는 노드로 변경

3. 앞의 2단계를 반복하다가, 현재 노드의 링크가 비어 있으면 종료

current = node1 while current.link != None : current = current.link print(current.data, end= ' ') print('\r')

노드 삽입 ㅡ 리스트 중간에 데이터 삽입하기

1. 새 노드를 생성하고 데이터 입력

2. 새 노드의 링크에 node2의 링크를 복사 (새 노드와 node2의 링크는 모두 node3을 가리키고 있음)

3. node2의 링크에 새 노드를 연결

newNode = Node() newNode.data = "정문" newNode.link = node2.link node2.link = newNode

노드 삭제 ㅡ 리스트 중간 데이터 삭제하기

1. 삭제할 node3의 링크를 바로 앞 노드의 링크로 복사한다. 그러면 node2가 node4를 가리키게 된다.

2. node3을 삭제한다.

node2.link = node3.link del(node3)

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

* 헤드 head : 첫 번째 노드

* 현재 current : 지금 처리중인 노드

* 이전 pre : 현재 처리중인 노드의 바로 앞 노드

# 처음에는 모두 비어있으면 되므로 다음과 같이 초기화 memory = [] # 리스트 head, current, pre = None, None, None # 데이터 입력 node = Node() node.data = dataArray[0] head = node memory.append(node) # 두 번째 이후 데이터 입력 pre = node node = Node() node.data = data # 두 번째 이후 노드 preNode.link = node memory.append(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() # 전역변수 선언부 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)

노드 삽입 ㅡ 리스트 중간에 노드 삽입

1. 헤드 head 에서 시작해서 현재 current 노드가 "사나"인지 확인

2. 현재 노드를 이전(pre)노드로 지정하고, 현재 노드를 다음 노드로 이동한 뒤 현재 노드가 "사나"인지 확인

3. 현재 노드가 "사나"일 때까지 위 단계들을 반복

4. 현재 노드가 "사나"라면 우선 새 노드를 생성한 후 새 노드의 링크를 현재 노드로 지정

5. 이전 노드의 링크를 새 노드로 지정

current = head while current.link != None : pre = current current = current.link if current.data == "사나" : node = Node() node.data = "솔라" node.link = current pre.link = node

노드 삽입 ㅡ 리스트 마지막에 노드 삽입

1. 중간 노드 삽입 과정과 동일하므로 없는 데이터인 "정문"을 찾는다

2. 마지막 노드까지 "정문"을 찾지 못했다면 우선 새 노드를 생성한 후, 현재 노드의 링크를 새 노드로 지정한다

node = Node() node.data = "문별" current.link = 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 # 전역변수 선언부 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)

노드 삭제 ㅡ 첫 번째 노드 삭제 & 그 외 노드 삭제

current = head # 현재 노드를 삭제할 노드인 헤드와 동일하게 만듦 head = head.link # 헤드를 삭제할 노드(다현 노드)의 링크가 가리키던 정연 노드로 변경 del(current) current = head while current.link != None : pre = current current = current.link if current.data == "쯔위" : pre.link = current.link del(current) # 노드 삭제 함수의 완성 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)

from http://moony96.tistory.com/5 by ccl(A) rewrite - 2021-12-22 11:26:24