링크드 리스트

 

간단한 메모리 사용 구조

CPU	Memory DRAM	Storage HDD 저장장치
		컴퓨터 안에 들어잇는 하드디스크 파일, 데이터저장
처리속도 가장 빠름	데이터 빠르게 저장,가져옴 가격이 매우 고가 용량 아주 작음 전원 끄면 데이터 사라짐	가격이 저렴 용량이 큼 전원이 꺼져도 데이터 저장

CPU 와 Storage 속도 차이가 많이 나기 떄문에

storage에 저장되어 있는 프로그램, 파일 -> Memory 로 옮겨 -> CPU에서 처리

 

데이터 스터력쳐의 미션 = 메모리의 효율적 사용  ❗️

 

 

 

메모리

 

RAM (Random Acess Memory)

adress 각각의 위치에 데이터 저장

각각의 주소에 접근하는 시간이 동일 

-> adress 를 알고 있으면 매우 빠르게 처리할 수 있음

 

 

리스트

메모리를 사용한느 방식에 큰 차이가 있음

Array list	Linked List
같은 element들이 연속적으로 붙어있음	각각의 element들이 흩어져 있음  연결 되어 있음

 

 

링크드 리스트

element < node & vertex

구조를 설명하기 위한 표현 

Data field	데이터 저장
Link field	다음 node 가 무엇인지
Head field	첫 번째 node  무엇인지 정보

 

 

 

 

 

 

 

 

링크드 리스트의 삽입 & 삭제 & 조회

|첫 번째 node에  데이터 삽입 시

temp를 가장 앞에 추가할 떄
1) node 생성
2) temp.next =head  
3) head 에 temp 값 넣기

 

|중간 node에 데이터 삽입 시

삭제변수 1 = 삭제할 node
앞의 node. next.next = 뒤의 node

1) 앞쪽에 있는 node.next =temp
2) temp.next = 뒤쪽에 있는 node

이처럼 링크드 리스트는 중간에 데이터를 추가할 때 간단함

하지만, Array리스트는 중간 삽입 시 하나씩 뒤로 밀어야함 

 

 

|node 삭제

제거할 node = 변수지정
앞의 node.next= 앞의node.next.next (뒤의 node)
delete node (node 삭제)

 

 

조회 시 각 list의 Trade off 관계 

	Array list	Linked List
추가 / 삭제	느림	빠름 * O(1)의  시간에 가능
인덱스 조회	빠름	느림 * O(n)의 시간 소요

 

 

 

* O(1) 의 관한 설명 하단게시글 참고

https://rrecoder.tistory.com/63

빅 오 표기법이란(Big O) - 알고리즘과 시간복잡도로 보는 빅 오 표기법

 

 

단일 연결 리스트	이중 연결 리스트	원형 연결 리스트

출처)ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8 위키백과

 

 

ADT

추상적 자료형 ( Abstract Data Type )

class 와 해당 메소드만 정의

실제 자료구조는 중요하지 않고 메서드를 구현하면 됨