[자료구조] Python - 리스트(list)

리스트의 연산 

• insert(pos, e): pos 위치에 새로운 요소 e를 삽입 
• delete(pos): pos 위치에 있는 요소를 꺼내서 반환 
• getEntry(pos): pos 위치에 있는 요소를 삭제하지 않고 반환 
• isEmpty(): 비어있으면 True, 아니면 False
• isFull(): 가득 차 있으면 True, 아니면 False
• size(): 리스트에 들어있는 전체 요소의 수 반환 

연결 리스트(Linked list)

노드로 데이터와 링크를 저장하고 있는 구조로, 링크에는 다음 노드의 주소를 저장하고 있음 

 

배열(Array) vs 연결리스트(linked list)

• 배열 
  • 배열은 모든 요소의 크기가 갖고 연속된 메모리 공간을 갖고 있어 특정 인덱스에 접근이 쉬움 
  • 메모리가 고정되어 유연성이 부족 
  • 삽입, 삭제 연산에 시간이 오래 걸림 
• 연결리스트 
  • 연속된 메모리 공간이 아니기 때문에 특정 인덱스에 접근하는 경우 시간이 오래 걸림 
  • 메모리를 유연하게 추가하거나 삭제할 수 있음 
  • 중간에 데이터 삽입, 삭제가 용이함