연결리스트(Linked Lists)
연결리스트 (Linked Lists)
- 선형배열이 번호가 붙여진 칸에 원소들을 채워넣는 방식이라고 하면, 연결리스트는 각 원소들을 줄줄이 엮어서
관리하는 방식임
- 연결리스트는 원소들이 링크라고 불리는 고리로 연결되어 있으므로, 가운데를 끊어 하나를 삭제하거나 삽입하기가 쉬움
- 하지만 메모리 소요가 큼
추상적 자료구조
Data ex) 정수, 문자열 ,레코드 .....
A set of operations ex) 삽입 삭제 순회/ 정렬 탐색
Node - data
- link(next)
리스트의 맨앞 : head
리스트의 맨끝 : tail
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount =0
self.head = None
self.tail = None
연산 정의
1. 특정 원소 참조(K번째)
순서 셀땐 1부터 시작함. 0을 밖으로 빼고 다른 용도에 사용할 것!
k번째 노드로 찾아간다.
class LinkedList에 있는 메소드 getAt() : pos번째의 노드를 뽑아서 노드를 리턴하겠다.
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
2. 리스트 순회
def traverse(self):
answer =[]
i =1
while i <= self.nodeCount:
answer.append(self.getAt(i).data)
return answer위 코드는 바람직하지 않다.
이유는 getAt을 호출 할 때마다 head부터 시작해서 순회하고 append한다.
append할 때마다 순회를 해야함
코드의 핵심은 하나씩 순회할 때마다 바로 append를 해야함
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def traverse(self):
bins = []
curr = self.head
while curr != None:
bins.append(curr.data)
curr = curr.next
return bins
# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
return 0--> 바로 getAt이 아닌 traverse 코드에서 해결하자!
처음에 self.head로 첫번째 지점을 정해주고 while문안에서 순회시키는 것!
이렇게 하면 호출할 때마다 처음부터 순회할 필요없이 순회할때 마다 추가되겠지
3. 길이 얻어내기
nodeCount return
4. 원소 삽입
def insertAt(self, pos, newNode):
prev = self.getAt(pos - 1) #삽입하려는 위치의 전 노드를 받고
newNode.next = prev.next # 전 노드의 next값을 새로운 노드의 next값으로 연결
prev.next = newNode # 새로운 노드의 값을 전 노드의 next값으로 재연결
self.nodeCount += 1
** 코드 구현 주의사항**
(1) 삽입하려는 위치가 리스트 맨 앞일 때
->prev 없음
->head조정 필요
(2) 삽입하려는 위치가 리스트 맨 끝일 때
->Tail 조정 필요
(3) 빈 리스트에 삽입할 때 ?
: 이 두 조건에 의해 처리됨
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
if pos ==1:
newNode.next = self.head #첫번째 순서에 삽입시 head 처리
self.head = newNode
else:
prev = self.getAt(pos - 1)
newNode.next = prev.next
prev.next = newNode
if pos == self.nodeCount +1: #맨 마지막에 node 삽입시 tail처리
self.tail = newNode
self.nodeCount += 1
return True!!! 여기서 코드를 더 개선해 보자면 !!!
tail조건을 맨 앞으로 빼는 것!
더 효율적인 코드가 된다.
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
if pos ==1:
newNode.next = self.head
self.head = newNode
else:
if pos ==self.nodeCount + 1:
prev = self.tail
else:
prev = self.getAt(pos - 1)
newNode.next = prev.next
prev.next = newNode
self.nodeCount += 1
return True- 복잡도
맨 앞에 삽입하는 경우 : o(1)
중간에 삽입하는 경우: o(n)
맨 끝에 삽입하는 경우 : o(1)
5. 원소 삭제
pos가 가리키는 위치의 node를 삭제하고 그 node의 데이터를 리턴하자.
(1) 삭제하려는 node가 맨 앞의 것일 때
->prev 없음
->head 조정 필요
(2) 리스트 맨 끝의 node를 삭제할 때
-> tail 조정 필요
(3) 유일한 노드를 삭제할 때
이 두 조건에 의해 처리되는가...??
(4) 삽입처럼 맨끝 삭제할 때
순회없이 한번에 삭제할 수 있는 방법이 없다.
즉 prev를 꼭 찾아야되므로 앞에서 부터 찾아봐야한다.
- 복잡도
맨 앞에 삽입하는 경우 : o(1)
중간에 삽입하는 경우: o(n)
맨 끝에 삽입하는 경우 : o(n)
5. 두 리스트 합치기
def concat(self, L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount