연결리스트 level 1

리스트(List)

---

1) 리스트(List)

 - 여러 개의 데이터를 하나의 변수로 저장 및 관리할 때 사용되는 집합

 - 리스트 내 서로 다른 자료형의 데이터들을 저장할 수 있을 정도로 배열 보다 높은 융통성을 갖는다
 - 배열과 마찬가지로 각 원소들엔 index라는 번호가 붙여진다

 

2) 리스트(List)관련 method 정리

  ① 원소 추가하기

    - append(x) : list 끝에 요소x를 추가함

    ※ append(x) vs +=(+)

      * +=는 append method 보단 extend method에 더 가깝다.(두 list를 합쳐 새로운 list를 만듬)
      * 반면, append는 하나의 list 끝에 항목을 추가함.
      * 따라서, 겉으론 += 연산이 깔끔해 보일 수 있으나 append method를 사용하는 것이 더 효율적이다.

  ② 원소 삭제하기

    - del : 값 대신 인덱스를 사용하여 항목을 삭제함. 

             list에서 슬라이스를 삭제하거나 전체를 비우는 데도 사용될 수 있다.

>>> num = [1, 2, 3, 4, 5]
>>> del num[0]
>>> num
[2, 3, 4, 5]

    - remove(x) : list내 값이 x와 같은 첫 번째 항목을 삭제함. 

>>> num = [1, 2, 3, 4, 5]
>>> num.remove(2)
>>> num
[1, 3, 4, 5]

     ※ del vs remove
      * list내 특정 데이터를 삭제 시 '값'을 사용할 시 remove method, 인덱스로 삭제 시 del 사용
      * del은 단순 삭제인 것에 반해, remove mothod는 list 내 값을 찾아 삭제함

    - pop(x) : 지정한 위치에 값을 반환 후 삭제
    - clear(x) : 리스트 내 모든 데이터를 삭제

 

연결리스트

---

1) 연결리스트

3 of Nodes

  - 추상적 자료형인 리스트를 구현한 자료구조로서, 데이터와 포인터를 가진 노드(Node = Data + Link)들을 한 줄로 늘어놓은 것

  - Node 내의 Data는 다른 구조로 이루어질 수 있음 ex) 문자열, 레코드, 또는 다른 연결 리스트 등

  - 리스트의 맨 앞 Node → Head, 리스트의 마지막 Node → Tail

 

  ① 자료 구조 정의 

# 노드가 1개 뿐인 연결리스트
class Node :
	del __init__(self, item) :
    	self.data = item
        self.next = None

# 비어있는 연결  리스트
# Head와 Tail모두 아무것도 가리키지 않은 상태
class LinkedList :
	def __init__(self) :
    	self.nodeCount = 0
        self.head = None
        self.tail = None

 

  ② 연결 리스트 연산

    1. 특정 원소 참조(k 번째)

def getAt(self, pos):						# pos번째의 노드 자체를 return하는 것이 목표
		if pos < 0 or pos > self.nodeCount:
			return None

		i = 1						# i를 1롤 하여 curr이 해당 리스트의 첫 번째 노드를 가리키도록 함 								
		curr = self.head
		while i < pos:					# i가 pos보다 작은 동안에 i를 1씩 증가시키면서 curr에 curr.next를 가리키게 하면	 
			curr = curr.next			# curr이 원하는 pos 번재 Node를 가리키게 됨 
			i += 1

		return curr

    2. 리스트 순회 * 실습

def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result

    3. 길이 얻어내기 

self.nodeCount()

    4. 원소 삽입

  - pos가 가리키는 위치에 newNode를 삽입하는 것

  - 성공/실패에 따라 True/False를 return

def insertAt(self, pos, newNode) :
	prev = self.getAt(pos - 1)		# 0. newNode가 들어갈 위치를 찾는다
    	newNode.next = prev.next		# 1. newNode의 링크(포인터)를 pos 번째 Node로 조정하고
   	prev.next = newNode			# 2. pos - 1 번째 링크를 newNode를 가르키도록 조조정한 후
    	self.nodeCount += 1			# 3. nodeCount를 1 증가시킨다

※ 주의 사항

  1) 삽입하려는 위치가 리스트 맨 앞일 때 → prev가 없으므로 head 조정 필요

  2) 삽입하려는 위치가 리스트 맨 끝일 때 → prev == Tail로 하여 getAt 메소드를 호출할 필요가 없다

  3) 빈 List를 처리해야할 경우가 있음

 

• 주의 사항 고려한 원소 삽입 메소드

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

	if pos == self.nodeCount + 1:
    	self.tail = newNode

	self.nodeCount += 1
    	return True

  ※ 연결 리스트 원소 삽입의 복잡도

    - 맨 앞에 삽입하는 경우 : O(1)

    - 중간에 삽입하는 경우 : O(n)

    - 맨 끝에 삽입하는 경우 : O(1)

 

    5. 원소 삭제

  - pos가 가리키는 위치의 Node를 삭제하고 그 Node의 Data를 return

def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount :
            raise IndexError
            
        curr = self.getAt(pos)			
        result = 0
        
        if pos == 1 :				# * 삭제하려는 node가 맨 앞 Node(Head) 일 때
            self.head = curr.next
            if self.nodeCount == 1 :
                self.tail = self.head
        else :
            prev = self.getAt(pos - 1)		# ** insert와 달리 tail을 가지고 prev의 값을 찾을 방법이 없으므로 앞에서부터 찾아와야 함
            prev.next = curr.next		# 1. prev링크를 curr 다음 node가 가리키는 곳으로 가리키게 하고	
            if pos == self.nodeCount :	
                self.tail = prev
        
            
        result = curr.data   			# 2. curr 값을 return
        self.nodeCount -= 1			# 3. nodeCount를 1만큼 감소 시키게함
        
        return result

  ※ 연결 리스트 원소 삭제의 복잡도

    - 맨 앞에 삽입하는 경우 : O(1)

    - 중간에 삽입하는 경우 : O(n)

    - 맨 끝에 삽입하는 경우 : O(n)

 

    6. 두 연결 리스트의 연결

 

    def concat(self, L):			
        self.tail.next = L.head		# 1. self.tail 링크를 L head를 가리키게 함
        if L.tail:
            self.tail = L.tail		# 2. self.tail을 L tail롤 지정
        self.nodeCount += L.nodeCount