링크드 리스트 공부

작성일

개요

※ 자료구조란 ? 데이터와 데이터를 체계적으로 구조화한 것 ex) 순차적으로 데이터를 구조화 -> 리스트 / 데이터를 쌓듯이 구조화 -> 스택

링크드 리스트란 자료구조의 일종. 어떤 데이터 덩어리(노드)를 저장할 때, 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다. 쉽게 표현하자면 자료를 비엔나 소세지 마냥 줄줄이 엮어놓은 것이다. (노드와 링크를 구조하시킨 것. 링크는 연결고리, 노드는 그릇)

배열과 달리 새로운 자료, 즉 노드를 뒤에 연결하거나 중간에에 노드 몇 개를 껴넣는 것이 쉽다. 그러나 배열에서는 자료마다 번호가 있어서 특정한 자료를 불러내기가 편리한 반면, 연결리스트는 자료 번호가 없이 그저 연결관계만 있기 때문에 특정 노드를 불러내기 어려운 단점이 있다.

배열은 배열을 선언할 때, 저장할 공간을 미리 저장해야하지만 리스트는 계속 동적으로 줄였다 늘였다 할 수 있다.

생활코딩 링크드 리스트 기본 개념 공부

컴퓨터 3가지 중요한 부품 CPU, 메모리(RAM) , 스토리지(HDD,SSD)

메모리 : 속도가 빠르다, 용량이 작다. 휘발성 스토리지 : 속도 느림, 용량 크고, 비휘발성

첫 번째 노드가 무엇인가를 의하는 정보를 헤드필더에 적는다. 데이터필드는 값이 들어간다. 데이터 필드의 링크 필드에는 다음 링크를 가리키는 주소가 들어간다.

visual.net / 링크드 리스트 visualgo

#####삽입하기

시작부분에 추가

  1. 새로운 노드 생성 Vertex temp = new Vertex(input
  2. 새로운 노드의 다음 노드로 첫번째 노드를 가리킨다. temp.next = head
  3. 새로 만들어진 노드가 첫번째 노드가 되도록 head의 값을 변경 head = temp

중간에 추가 추가하고자 하는 노드의 앞을 temp1이란 값을 잡고, 노드의 뒤를 temp2로 잡는다.

  1. Vertex temp1 = head temp1이라는 임시 변수가 head를 가리키게 한다.
  2. while(--k!=0) temp1= temp1.next 6이라는 숫자가 담겼다고 하자.
  3. Vertex temp2 = temp1.next 즉 temp1의 오른쪽 temp2가 23이라고 하면 temp2에 23이 담겼다.
  4. Vertax newVertex = new Vertex(input) // 노드 생성
  5. temp1.next = newVertex // 삽입하고자 하는 노드를 생성
  6. newVertex.next = temp2 새로 생성한 노드의 오른쪽을 temp2로 변경

데이터의 제거

  1. 첫 번째 노드 선택해서 next로 간다
  2. 삭제한 노드 선택
  3. 삭제하기 앞서서 삭제할 노드의 앞의 노드를 삭제할 노드 다음의 노드로 선택
  4. 삭제할 노드를 메모리상에서 제거

데이터 조회

  1. 헤드의 노드를 통해서 첫 번째 노드 찾기
  2. 아니면 다음노드로 찾기
  3. 값을 찾으면 그 값을 리턴
이중연결리스트

데이터 삽입 10 - 20 - 30 - 40 이 이중 연결리스트로 구현되어 있다고 가정

  1. 25를 생성
  2. 25를 다음 노드로 30을 연결
  3. 30이전의 노드로 25를 연결
  4. 20의 다음 노드로 25를 연결
  5. 25의 이전노드로 20을 연결

데이터 제거

  1. 삭제하려는 노드 이전의 20을 찾는다.
  2. 삭제하려는 노드 30도 찾는다
  3. 삭제하려는 노드 30도 찾는다.
  4. 30을 삭제한다.
  5. 20의 다음 노드로 40을 지정한다
  6. 40의 이전 노드로 20을 지정한다.

단순 연결 리스트

데이터를 저장하는 노드와 바로 그 다음노드를 가리키는 링크하나로 구성되어 있다.

image

Q) 가장 먼저 있는 데이터 A를 누가 가리키냐? -> 리스트의 머리(head) 필요.

head -> 일반적으로 전역변수로 선언되어 어느 곳에서도 접근이 가능하고, 소멸되지 않게 한다.

Q) 연결리스트의 마지막 노드는?

마지막 노드 역시, 무언가를 가리켜야 하는데 마지막을 나타내는 꼬리(tail)을 만들어서 이를 해결한다. 또는 NULL

typedef struct node {
	int key;
    struct node *next;
} Node;

연결 리스트의 구조

  • 노드 = 데이터 필드 + 링크 필드
  • 헤드 포인터 = 첫 번째 노드를 가리키는 포인터
  • (맨 마지막 노드의 링크필드는 NULL)

※

참고자료

http://home.konkuk.ac.kr/~khidpig/lecture/2018_1/pp_a/Chapter17_lec.pdf

http://terms.naver.com/entry.nhn?docId=2270421&cid=51173&categoryId=51173

https://opentutorials.org/module/1335/8821

나무위키 연결리스트

0%