연결리스트(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