자료구조 알고리즘 - 이론

Linked list
컴퓨터에 자료를 저장하는 구조의 한 종류, 일렬로 연결된 데이터를 저장할 때 사용. 다음 데이터의 주소를 가지고 있음. 데이터를 중간에 삽입 가능. 앞에 노드가 가지고 있던 주소를 자기가 갖고, 앞에 노드에게는 다음 순서를 알려줌. 링크를 삭제하는 것도 가능. 속도가 배열 보다 느림. 배열은 추가/삭제가 어렵고 번거로움. 길이가 정해지지 않은 데이터 핸들링시 linked list 사용.

단방향/양방향 Linked list
양방향 삽입/삭제시 X자로 양쪽에서 노드 데이터를 끌어옴.

Linked List 중복값 삭제
정렬되어 있지 않는 linked list에서 버퍼를 사용하지 않고 중복값을 삭제하자. 버퍼를 사용할 때는 hashset에 저장해서 사용할 수 있음. 버퍼 대신 포인터를 사용. N/R. 두 개 포인터 첫번째 노드 가리키면 R러너가 가서 확인 후 삭제.

단방향 linked list 뒤부터 세기
단방향은 앞에서 부터 시작함.
방법 1 : 처음 노드 부터 1개씪 뒤로 이동하면서 전체 노드 개수를 카운트.
방법 2 : 재귀호출. 조건이 만족될 때까지 나 자신을 계속 호출. 나올 때 뒤에서 부터 나옴. 끝까지 들어갔다가 나올때 세면서 나옴. 첫번째 노드를 가지고 함수를 호출. 노드가 null이 될때까지 카운트 하고 하나씩 +1을 함.
방법 3 : 포인터 2개 선언. 1개를 K만큼 먼저 앞으로 가게 함. 이후 포인터를 둘이 동시에 null을 만날 때 까지 하나씩 이동.

단방향 linked list 중간노드 삭제
첫번째 노드가 어디있는지 모르고, 오직 삭제할 노드만 갖고 있다. 앞에 노드의 주소를 뒤에 있는 애로 바꿔치기 하면 자동 삭제. 다음에 있는 노드를 삭제할 노드에 엎어씌우자. 이후 중복 값 지우기.

linked list digit 합산 알고리즘
문제 : 어떤 숫자를 자리수 별로 한개씩 linked list에 담았따. 그런데 1의자리가 헤더에 오도록 거꾸로 담았다. 이런식의 linked list 두개를 받아서 합산하고 같은식으로 linked list에 담아서 반환하라.
각 숫자의 자리수 별로 나눠서 노드에 넣어둠. ex) 6->4->3 => 346

linked list 교차점찾기
교차점은 값이 아닌 주소로 찾아야함. 두개의 리스트가 중간에 합쳐지는 것. 첫번째 리스트와 두번째 리스트의 노드를 비교해야함. 리스트의 끝을 맞춰줌. 2개의 리스트 길이를 뒤를 기준으로 맞춰서 돌면서 교차점을 찾기.

linked list 루프찾기
루프가 시작되는 노드 찾기. 어떤 노드의 넥스트 값이 이미 그 리스트에 연결되어 있는 다른 노드를 가르키고 있을 때 루프가 생김. 두개의 포인터 사용. 각 포인터가 2개/1개씩 돌면서 만나는 점을 찾기. K = K/루프길이