연결리스트 정의와 실습

 

 

 

 

In [2]:

#7강 연결리스트
'''추상적 자료구조
data : 정수, 문자열, 레코드, ..
a set of operations : 삽입, 삭제, 순회... ,정렬,탐색..

기본적 연결 리스트
67 -> 34 -> 58 ->끝
67 : Head
노드숫자 : 3
58:tail
각각 노드에는 데이터와 링크(다음주소)를 가지고 있음
class Node:
    def__init__(self,item):
        self.data=item
        self.next=None

class LinkedList:
    def__init__(self):
        #노드갯수,head,tail 초기화
        self.nodeCount=0
        self.head=None
        self.tail.None

연산 정의
1. 특정 원소 참조(k번째) 2. 리스트 순회 3. 길이 얻어내기
4. 원소 삽입 5.원소 삭제 6.두 리스트 합치기

1. 특정 원소 참조
1     2     3 (인덱스 1~3 지정)
67 -> 34 -> 58 ->끝

def getAt(self,idx):
#인덱스가 범위가 벗어나면 안됨
    if idx<=0 pr idx>self.nodeCount:
        return None
    i=1
#첫번째 리스트(head) 가르킴
    curr=self.head
    while i<idx:
#현재의 다음
        curr=curr.next
        i+=1
    return curr

배열과 비교한 연결 리스트
              배열[O(1)]         연결리스트[O(n)]
저장공간       연속한 위치       임의의위치
특정 원소지칭  매우 간편        선형탐색과 유사'''
print('7강끝')

 

 

7강끝

 

In [2]:

#7강 실습: 연결 리스트 순회 구현하기

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):
        L=[]
        #현재노드를 시작 노드로 지정
        curr=self.head
        while curr is not None:
        #현재 노드 데이터를 결과 리스트에 추가
            L.append(curr.data)
        #다음노드로 연결
            curr=curr.next
        return L

# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
    return 0

 

In [3]:

#8강 연결 리스트
'''4. 원소 삽입 5.원소 삭제 6.두 리스트 합치기
4. 원소의 삽입
[pos-1]           self[pos]
        newNode
def insertAt(self,pos,newNode)
    prev=self.getAt(pos-1)
    newNode.next=prev.next
    prev.next=newNode
    self.nodeCount+=1

주의
1.삽입하려는 위치가 리스트 맨 앞이면 prev선언 필요없음
단 Head가 가르키게 한다.
2.삽입하려는 위치가 리스트 맨 끝이면,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
    #삽입하려는 위치가 맨 끝일때
    if pos==self.nodeCount+1:
        self.tail=newNode
    self.nodeCount+=1
    return True

 

In [19]:

#이 코드 살펴볼 것
class Node:
    def __init__(self, item):
        # 1. 노드 객체 생성자:데이터(item)를 받아 노드 초기화
        self.data = item
        # 다음 노드를 초기화합니다.
        self.next = None 

class LinkedList:
    # 연결 리스트 객체 생성자: 노드 개수, 첫 번째 노드(헤드),
    # 마지막 노드(테일) 초기화
    def __init__(self):
        
        self.nodeCount = 0
        # 첫 번째,마지막 노드를 초기화
        self.head = None
        self.tail = None
    
    #연결 리스트 객체를 문자열로 표현할 때 사용되는 메서드
    def __repr__(self):
        
        if self.nodeCount == 0:
            return 'LinkedList: empty'
        s = ''
        curr = self.head
        
        # 연결 리스트의 각 노드 데이터를 문자열로 표현하여
        # 연결해서 반환
        while curr is not None:   
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
            curr = curr.next
        return s
    # 4. 주어진 위치(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
    #주어진 위치(pos)에 새로운 노드(newNode)를 삽입하는메서드
    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        # 만약 위치(pos)가 1일 경우
        if pos == 1:
            # 새로운 노드를 현재 첫 번째 노드로 연결
            newNode.next = self.head
            # 헤드를 새로운 노드로 업데이트
            self.head = newNode
        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                #이전 노드(prev)를 찾음
                prev = self.getAt(pos - 1)
            # 새로운 노드를 이전 노드 다음에 연결
            newNode.next = prev.next
            # 이전 노드를 새로운 노드 다음에 연결
            prev.next = newNode  
        # 만약 위치(pos)가 리스트의 끝일 경우, 테일을 업데이트
        if pos == self.nodeCount + 1:
            self.tail = newNode
        # 노드 개수 증가
        self.nodeCount += 1 
        return True
    # 연결 리스트의 노드 개수를 반환
    def getLength(self):
        return self.nodeCount
    
    # 연결 리스트의 노드 데이터를 리스트로 반환
    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result
    
    # 현재 연결 리스트에 다른 연결 리스트(L)를 이어붙이는 메서드
    def concat(self, L):
        # 현재 연결 리스트의 테일을 다른 연결 리스트의 헤드에 연결
        self.tail.next = L.head
        # 다른 연결 리스트의 테일이 존재하면 업데이트
        if L.tail:
            self.tail = L.tail
        # 전체 노드 개수 업데이트
        self.nodeCount += L.nodeCount

 

In [20]:

a=Node(67)
b=Node(34)
c=Node(28)
L=LinkedList()
L

 

Out[20]:

LinkedList: empty

 

In [21]:

L.insertAt(1,a)

 

Out[21]:

True

 

In [22]:

L.insertAt(2,b)

 

Out[22]:

True

 

In [23]:

L

 

Out[23]:

67 -> 34

 

In [24]:

L.insertAt(1,c)

 

Out[24]:

True

 

In [25]:

L

 

Out[25]:

28 -> 67 -> 34

 

In [ ]:

#연결 리스트 원소 삽입의 복잡도
'''맨 앞에 삽입할때 O(1)
중간에 삽입할때 O(n)
맨 끝에 삽입할때 O(1) : tail 포인터 사용할때'''
#연결 리스트 연산-원소의 삭제
'''r=L.popoAt(pos)

+괄호 안은 인덱스 번호, 밖은 객체나 변수

[pos-1]  [pos]   [pos+1]
1. 인덱스 pos-1의 변수 prev로, pos의 변수 curr로 지정한다.
prev[pos-1]  curr[pos]   [pos+1]
2. prev의 다음값(prev.next)을 curr.next[pos+1]로 한다. (다음 포인터 지정)
3. curr의 데이터 r 추출후 nodeCount-=1

주의사항 (삭제하려는 node가)
self.head
  [pos]      [pos+1]
1. 맨 앞이면 (prev 없음, Head 재지정필요)
         self.tail
[pos-1]    [pos]
2. 맨끝이면 (tail 재지정필요, pos의 다음값도 같이 옮김)
3. 유일한 노드를 삭제할때?'''

 

In [ ]:

#연결리스트 합침
'''def concat(self,L):
연결리스트 self의 뒤에 L을 붙임

self.head-> self.tail   /   L.head -> L.tail

self.tail.next=L.head
self.tail=L.tail

def concat(self,L):
    self.tail.next=L.head
    #L이 비었을 경우 체크
    if L.tail:
        self.tail=L.tail
    self.nodeCount+=L.nodeCount
이렇게 배열과 달리 한번에 연결할수 있다는게 연결리스트의 장점'''

 

In [26]:

#8강 실습: 연결 리스트 노드 삭제하기

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

    #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

    #    [pos-1]           [pos]
    #            newNode
    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        
        #         self.head
        #           [pos]
        # newNode
        if pos == 1:
            #현 self.head을 삽입값 다음값으로 한다. 
            newNode.next = self.head
            #새로운 삽입값을 self.head로 선언
            self.head = newNode
        #그 외
        else:
            #삽입하려는 위치가 마지막일때.
            #           self.tail
            #[pos-1]      [pos]
            #                      newNode
            if pos == self.nodeCount + 1:
                #현 꼬리값을 prev로 만듦
                prev = self.tail
            
            #그외 경우
            # [pos-1]          [pos]
            #         newNode
            else:
                #getAt을 이용해 이전(pos - 1)값을 찾는다.
                prev = self.getAt(pos - 1)
            
            #이전값의 다음값을 삽입값의 다음값으로 지정
            newNode.next = prev.next
            #newNode를 삽입값의 다음값으로 지정
            prev.next = newNode
       
        #삽입하려는 위치가 마지막일때.
        if pos == self.nodeCount + 1:
            #newNode를 꼬리값으로 만듦
            self.tail = newNode
        self.nodeCount += 1
        return True

    #[pos-1]    [pos]     [pos+1]
    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return False
        #삭제하려는게 맨 앞일때
        #   [pos]     [pos+1]
        #self.head
        if pos == 1:
            #현재 head를 curr로 선언
            curr = self.head
            #현재 데이터 추출
            data=curr.data
            #curr의 다음값을 head로 재지정
            self.head = curr.next
        
        #[pos-1]    [pos]     [pos+1]
        else:
            #삭제할 값의 이전 노드(pos - 1)를 찾음
            prev = self.getAt(pos - 1)
            #다음노드(prev.next)를 curr로 선언
            curr = prev.next
            #데이터 추출
            data=curr.data
            #curr의 다음값을 prev의 다음값에 삽입(curr 건너 뛰고 연결)
            prev.next = curr.next
            #삭제할 위치가 마지막이면, 이전값을 tail로 지정 
            if pos == self.nodeCount:
                self.tail = prev
            
        #만약 노드가 하나만 있는경우
        if pos==self.nodeCount and pos == 1:
            #그냥 빈 연결 리스트로 만듬
            self.tail = None
            self.head = None
        self.nodeCount -= 1
        return data

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

def solution(x):
    return 0

 

In [27]:

#9강 연결리스트
'''실사용예 : 스마트폰 실행중 파일 (삽입, 삭제가 쉽고 빠름)

조금 변형된 연결 리스트(맨 앞에 dummy node를 추가)
class LinkedList:
    def__init__(self):
        self.nodeCount=0
        self.head=Node(None)
        self.tail=None
        self.head.next=self.tail

연산 정의
1. 길이 얻어내기 2.리스트 순회 3. 특정 원소 참조(k번째)
4. 원소 삽입 5.원소 삭제 6.두 리스트 합치기

특징 : 처음에 dummy node(head)가 있어 prev가 항상 존재함, 
삽입 삭제후에도 head 선언 다시 안해도 됨.
마지막에 dummy node가 있어서 tail 선언 다시 안해도 됨.
즉 예외적 연산이 없어지고, 방식이 단순화된다.'''

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None

#주의 맨앞에만 더미노드, tail 은 아님
class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        #방식이 None-> Node(None)으로 바뀜
        #'비어있지만 더미부분이다.' 를 명시한것으로 보인다.
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
        return s

    #1. 길이 얻어내기
    def getLength(self):
        return self.nodeCount

    #2.리스트 순회
    def traverse(self):
        result = []
        curr = self.head
        #다음값이 존재하면
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result

    #3. 특정 원소 참조(k번째)
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
        
        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    #4. 원소 삽입 :prev가 일관되니 그냥 객체로 줘버림
    # prev 값은 insertAt메서드로 준다.
    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        
        #지난번엔 1부터 했는데 0으로 초기화
        #더미 노드를 사용하니 if pos==1일때
        #했던 부가 조건이 사라짐
        
        #처음만 더미노드가 있는 상황이라
        #마지막에 삽입할때 삽입값을 tail로 선언
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True

    #이미 구현한 insertAfter 이용 메서드
    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        
        # pos가 처음이 아니고, 마지막에 삽입하는 경우
        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        #그 외
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
    
    #5.원소 삭제
    # [pos-1]    [pos]      
    def popAfter(self, prev):
        # 마찬가지로 prev를 인자로 받는게 바뀜
        # prev 기준으로 curr 구해줌
        curr = prev.next
        # 현재 노드(curr)의 데이터(data)를 저장
        data = curr.data
        # 현재 노드(curr)가 없는 경우 None을 반환
        if curr is None:
            return None
        # 현재 노드(curr)가 마지막 노드인 경우
        elif curr == self.tail:
            # prev.next인 curr를 None으로 초기화
            prev.next = None
            # prev를 self.tail로 만듦 
            self.tail = prev
        
        # 그 외의 경우,
        else:
            # curr의 다음노드를 이전 노드의 다음 노드로 설정
            prev.next = curr.next
        # 연결 리스트의 노드 수를 1 감소
        self.nodeCount -= 1
        # 제거된 노드의 데이터(data)를 반환
        return data

    def popAt(self, pos):
        # 위치(pos)가 유효한 범위 내에 있는지 확인
        if pos < 1 or pos > self.nodeCount:
            raise IndexError("Index out of range")
        #범위내 있으면
        else:
            # 노드를 찾기위해 self.getAt(pos - 1)을 호출
            prev = self.getAt(pos - 1)
        # popAfter 메서드를 호출하여 이전 노드 이후의 노드를 
        # 제거하고 제거된 노드의 데이터 반환
        return self.popAfter(prev)
    
    #6.두 리스트 합치기
    def concat(self, L):
        #head에만 더미가 있는상황, 그래서 head 다음에 연결
        self.tail.next = L.head.next
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

 

In [ ]:

#10강 양방향 연결 리스트
'''양쪽으로 링크를 연결 (앞 뒤로 진행 가능)
dummy<->67 <-> 34 <-> 58 <-> dummy
next 다음
prev 이전
+리스트의 처음과 끝에 dummy node 삽입'''

class Node:
    def __init__(self, item):
        self.data = item
        #이전과 달리 prev 포인터 추가됨
        self.prev = None
        self.next = None


class DoublyLinkedList:

    # 끝 <- dummy(head) <-> dummy(tail) -> 끝 
    def __init__(self):
        self.nodeCount = 0
        # 양 끝에 더미노드
        self.head = Node(None)
        self.tail = Node(None)
        ''' 더미 노드는 연결 리스트의 시작과 끝을 나타내며 이전 노드가 
        없거나(null) 이전 노드를 가리킬 필요가 없습니다. 아래 코드는 
        이전 노드는 없음을 명시적으로 나타내기 위해 사용됨'''
        self.head.prev = None
        
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        #더미가 있음으로 .next하나 더 써줌
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
    
    #반대방향으로 순회
    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

    #이 경우, 항상 앞에서 부터 찾아가야해서 마지막껀 느림
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
        #절반보다 크면 앞쪽부터가 아닌 뒤(tail) 부터 앞으로
        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        #그 외는 정상 방향으로
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
        return curr

    def insertAfter(self, prev, newNode):
        #양쪽 방향이 있기 때문에 다음노드의 기준을 설정
        next = prev.next
        #링크 끊기전 연결
        newNode.prev = prev
        newNode.next = next
        #링크 끊음
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    #pos로부터 prev를 구해서 insertAfter에서 사용
    # [pos-1]      [pos]
    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
    
    #                 next
    #        newNode
    def insertBefore(self,next,newNode):
        #양쪽 방향이 있기 때문에 다음노드의 기준을 설정
        prev = next.prev
        #링크 끊기전 연결
        newNode.prev = prev
        newNode.next = next
        #링크 끊음
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
    
    # prev
    def popAfter(self,prev):
        #다음이 self.tail 즉 더미노드라면 뺄것이 없음
        if prev.next is self.tail:
            return None
        curr=prev.next
        data=curr.data
        prev.next=curr.next
        curr.next.prev=prev
        self.nodeCount-=1
        retrurn data
    
    #       next      
    def popBefore(self,next):
        if next.prev is self.head:
            return None
        curr=next.prev
        data=curr.data
        next.prev=curr.prev
        curr.prev.next=next
        self.nodeCount-=1
        retrurn data
        
    #특정번째 포지션 데이터 뽑아내기
    #        [pos]
    def popAt(self,pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError("Index out of range")
        prev=self.getAt(pos-1)
        next=prev.next
        data=next.data
        prev.next=next.next
        next.next.prev=prev
        return data
    
    #   ~self.tail  |  L.head~
    def concat(self,L):
        self.tail.prev.next=L.head.next
        L.head.next.prev=self.tail.prev
        if L.tail:
            self.tail=L.tail
        self.nodeCount+=L.nodeCount

 

In [ ]:

#11강 스택
'''자료를 보관할 수 있는 (선형)구조
넣을때는 한쪽 끝에서 밀어 넣고 : push 
꺼낼때는 같은 쪽에서 뽑아 꺼냄 : pop
후입선출 구조

#스택선언
S=Stack()
S.push(A)
S.push(B)
r1=S.pop()
r2=S.pop()
r3=S.pop() -> 스택 언더플로우 (꺼낼 데이터가 없음)

반대로 크기에 비해 push를 많이 하면 ->스택 오버플로우

스택의 추상적 자료구조 구현

(1)배열을 이용해 구현
파이썬 리스트와 메서드들 이용

(2)연결리스트를 이용하여 구현
양방향 리스트 이용

연산의 정의
size() : 현재 스택에 들어있는 데이터 원소수 구함
isEmpty() : 현재 스택이 비어 있는지 판단
push(x) : 데이터 원소 x를 스택에 추가
pop() : 스택의 맨위에 데이터 제거(또한 반환)
peek() : 스택의 맨위에 데이터 반환(제거는 안함)'''
from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

#배열로 구현
class ArrayStack:
    #빈 스택을 초기화
    def __init__(self):
        self.data = []

    # 스택의 크기를 리턴
    def size(self):
        return len(self.data)

    #스택이 비어 있는지 판단
    def isEmpty(self):
        return self.size() == 0

    #데이터 원소를 추가
    def push(self, item):
        self.data.append(item)

    #데이터 원소를 삭제
    def pop(self):
        return self.data.pop()
    
    #스택의 꼭대기 원소 반환
    def peek(self):
        return self.data[-1]

#이번에는 양방향 연결리스트를 이용
class LinkedListStack:
    #비어있는 연결리스트로 초기화
    def __init__(self):
        self.data = DoublyLinkedList()
    
    def size(self):
        return self.data.getLength()
    #비었는지 판단
    def isEmpty(self):
        return self.size() == 0
    
    #Node클래스(데이터와 포인터 초기화)를 불러옴
    def push(self, item):
        node = Node(item)
        #마지막 다음칸에 선언한 node를 삽입
        self.data.insertAt(self.size() + 1, node)
    
    #마지막 제거
    def pop(self):
        return self.data.popAt(self.size())
    #마지막 참조
    def peek(self):
        return self.data.getAt(self.size()).data

 

In [1]:

pip install pythonds

 

 

Collecting pythonds
  Downloading pythonds-1.2.1-py3-none-any.whl (14 kB)
Installing collected packages: pythonds
Successfully installed pythonds-1.2.1
Note: you may need to restart the kernel to use updated packages.

 

In [2]:

#스택을 라이브러리로 사용
from pythonds.basic.stack import Stack
S=Stack()
dir(S)

 

Out[2]:

['__class__',
 '__delattr__',
 '__dict__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__le__',
 '__lt__',
 '__module__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 '__weakref__',
 'isEmpty',
 'items',
 'peek',
 'pop',
 'push',
 'size']