[파이썬] DAY10 리스트 복습

복습

리스트

 

순차 리스트 : 삽입, 삭제 시 이동이 발생한다. (빈도수 증가)

파이썬의 리스트는 순차리스트이다.

하지만 파이썬의 가변의 특징으로 연결 리스트로 쓸 수 있다.(동적 할당)

다른 언어는 정적 할당이므로 순차리스트이다. 

인덱스가 있으면 모두 순차리스트이다.

 

 

 

단순 연결 리스트 구현 코드

class SList:
    class Node:
        def __init__(self,data, link): 
            self.data = data    
            self.next = link
                
    def __init__(self):                
        self.head = None               
        self.size = 0
        
    def is_empty(self):
        return self.size == 0
        
    def insert_front(self,item):
        if self.is_empty():
            self.head = self.Node(item,None) 
        
        else:
            self.head = self.Node(item,self.head)  
        self.size += 1
        
    
    def insert_after(self,item,p):
        p.next = self.Node(item,p.next)  
        self.size += 1
            
    def delete_front(self):
        if self.is_empty():                      
            raise Exception('노드가 없습니다.')
        else:  
            self.head = self.head.next   
            self.size -=1
            
    def delete_after(self,p):
        if self.is_empty():                      
            raise Exception('노드가 없습니다.')
        t = p.next
        p.next = t.next                  
        self.size -= 1 
    
    def search(self,target):
        p = self.head                    
        
        for k in range(self.size):
            if target == p.item:
                return k                 
            p = p.next
        return None                      
        
        
    def print_list(self):
        p = self.head
        
        while p:                         
            if p.next!=None:
                print(p.data, "->",end="")
            else:
                print(p.data)
            p = p.next

s = SList()
s.insert_front('data1')
s.insert_front('data2')
s.insert_after('data3',s.head.next)
s.insert_front('data4')
s.print_list()
s.delete_after(s.head)
s.print_list()
print('첫 노드 삭제 후 :\t\t',end="")
s.delete_front()
s.print_list()
print('첫 노드로 data5,data6 삽입 후 :\t', end="")
s.insert_front('data5')
s.insert_front('data6')
s.print_list()
s.delete_after(s.head.next.next)
print('data3 다음 노드 삭제 후 :\t',end = "")
s.print_list()

 

분석---------------------------------

 

 

클래스 안에 클래스

class SList:
    class Node:
        def __init__(self,data, link): 
            self.data = data    
            self.next = link

a = Node(1,2) 

외부에서는 노드를 함부로 만들 수 없다.

 

SList 안에 Node가 자동으로 생성된다.

 

a = SList.Node(1,2) 로 쓸 수 있다. 

 

 

첫 시작 주소를 적는 것이 중요하다

첫 노드를 받을 이름(head)를 꼭 있어야 한다. 

head : head pointer

    def __init__(self):                
        self.head = None               
        self.size = 0

 

 

머리에서 삽입

 

---

이중연결리스트

 

링크 필드가 두 개이다.

정방향, 역방향을 표현한다.

 

 

연결리스트와 달리 헤드 포인터가 아닌 헤드 노드를 만든다.

헤드가 하나인 연결리스트와 달리 헤드는 총 2개를 만든다. 양쪽으로 접근할 수 있는 구조가 된다.

 

 

 

양방향 삽입

정방향 삽입

 

 

역방향 삽입