연결 리스트 (Linked List) 2 - 각 작업 설명

원소 삽입 

맨 앞에 원소 삽입

맨 앞에 원소 삽입

__head : 첫 번째 노드를 가리키는 레퍼런스

newNode.item = x
newNode.next = __head
__head = newNode
__numItems += 1
...

 

중간, 맨 뒤에 원소 삽입

중간에 원소 삽입

맨 뒤에 원소 삽입

prev: 삽입 노드의 직전 노드를 가리키는 레퍼런스

newNode: 새로 삽입하려는 노드

newNode.item = x
newnode.next = prev.next
prev.next = newNode
__numItems += 1 
..

 

연결 리스트에 원소 삽입 알고리즘

if i == 0:
	newNode.item = x
    newNode.next = __head
    __head = newNode
    __numItems +=1
else:
	newNode.item = x
    newNode.next = prev.Next
    prev.next = newNode
    __numItems += 1

 

더미 헤드를 둔 연결리스트에서 삽입

리스트의 맨 앞에 원소가 들어 있지 않은 더미 헤드 노드(dummy head)를 놔두면, 위와 같이 나눠서 하지 않아도 된다. 

더미 헤드 노드가 있으면 삽입하고자 하는 노드 앞에 항상 직전 노드가 존재한다. 

 

원소 삭제

맨 앞에 원소 삭제

__head = __head.next
__numItems -= 1

 

 

중간&마지막 원소 삭제

prev.next = prev.next.next
__numItems -= 1

직전 노드가 삭제 노드를 건더뛰어 링크하게 만든다. 마지막인 경우네는 prev.next.next가 None이 되어 작동한다. 

 

연결 리스트의 원소 삭제하기

if i == 0:
	__head.next = __head.next.next
    __numItems -= 1 
else:
	prev.next = prev.next.next
    __numItems -= 1

 

더미 헤드 노드가 있는 연결리스트에서 삭제

더미 헤드 노드가 있으면 두 가지 경우로 나누지 않고 코딩할 수 있다. 

 

기타 작업 

연결 리스트의 i번째 원소 알려주기 

##  i번째 노드를 찾은 다음 그 노드의 원소 리턴
get(i):
	if i>=0 and i<= __numItems -1:
    	return __getNode(i).item
    else:
    	print("error in get(", i, ")")
        


## 리스트의 i번째 노드 알려주기 
__getNode(i):
	curr = __head
    for index in range(i+1):
    	curr = curr.next
    return curr



## x가 연결리스트이 몇 번 원소인지 알려주기
index(x):
	curr = __head
    for index in range(__numItems):
    	curr = curr.next
        if curr.item == x:
        	return index
    return -12345 
    
    
    
## 리스트가 비었는지 알려주기
isEmpty():
	return __numItem == 0



## 리스트의 총 원소 수 알려주기
size():
	return __numItems



## 리스트 깨끗이 청소하기
clear():
	newNode.next = None
    __head = newNode
    __numItems = 0

 

노드의 사용

노드 객체를 만드는 클래스 

class ListNode:
	def __init__(self, newItem, nextNode:'ListNode'):
    self.item = newItem
    self.next = nextNode