단순 연결 리스트 (Single Linked List)

연결 자료구조(Linked List)

선형리스트는 배열로 구성했었다. 원소의 위치를 찾긴 쉽지만, 삽입/삭제하기가 번거로웠다. 시간도 오래 걸리고, 오버헤드도 많이 생기고.

이를 해결하기 위한 자료구조로 '연결 자료구조'와 '비순차 자료구조'가 있다.

연결자료구조(Linked List)

• 원소의 논리적인 순서와 물리적인 순서가 일치할 필요 X → Link에 의해 원소들을 연결하기 때문. 논리-물리 순서 맞추기 위한 오버헤드 발생도 X

• 논리-물리 순서를 위한 오버헤드는 X. but 포인터에 대한 저장 공간은 추가로 필요 O

• 고정크기 메모리 공간 X

• 단순 연결 리스트(linked list), 이중 연결 리스트(double linked list), 원형 연결 리스트, 이중 원형 연결 리스트

노드(Node)

배열에서 원소는 그저 데이터만 저장했으면 됐었다. 왜? 논리적 주소 순서 == 물리적 주소 순서였기 때문에 주소는 계산만 잘 하면 됐으니까.

하지만 연결리스트는 아니다. 원소에 다른 원소와 연결되는 주소까지 저장해주어야 한다. 원소들 사이를 선으로 이어준다고 생각하면 된다.

이렇게 데이터+다음 원소의 주소를 저장하는 단위 구조를 노드(Node)라고 한다.

노드(Node) = 데이터 필드(Data Field) + 링크 필드(Link Field)

* 리스트의 맨 마지막 노드는 link부를 null로 해준다. 마지막이니까, 그 다음 노드를 가리키는 Link Field가 Null이 되는 것.

* header / trailer: 리스트의 맨 처음/ 맨 끝. data는 없고, 그냥 리스트 시작 노드와 끝 노드를 링크해준다.

Linked List 구현

C에서 노드는 구조체로 구현한다. Java에서는 클래스로 구현했었다.

  typedef struct _Node
  {
      char *data;
      struct Node *next;
  }Node;
  ​
  typedef struct _Header
  {
      struct Node *header;
  }header;
  ​
  Node newNode;
  newNode.data = "Hello";
  printf("%s\n", newNode.data);
  ​

노드는 데이터를 담고 있는 그릇.

link는 Node의 위치를 가리키기 때문에 포인터형을 쓴다.

자바로 할 때는 그냥 Node클래스 자체로 data와 link를 썼던 것 같다. (확실치 않음)

  //Java
  class Node
  {
      String data;
      Node next;
  }
  ​
  class LinkedList
  {
      public static void main(String args[])
      {
          LinkedList list = new LinkedList();
          Node header = new Node();
          Node tailer = new Node();
          
          header.next = tailer;
          list.addNode();
      }
      
      public void addNode()
      {
          ...
      }
  }

---

단순 연결 리스트(Single Linked List)

단순 연결 리스트(Single Linked List) : Link Field가 하나뿐인 리스트. (= Linear Linked List)

연결리스트에서 노드의 삽입/삭제는 <1. 새 노드의 연결 2. 기존 노드의 연결 삭제> 순서로 이루어져야 한다. 만약 둘의 순서를 바꾼다면, 즉, 기존 노드의 연결부터 삭제한다면, 새 노드를 어디에 끼워야 할 지 모르게 된다. 연결리스트는 노드들 간 연결로 위치를 알아내기 때문이다.

노드 삽입

1. 새 노드를 연결

2. 기존 노드의 연결을 새 노드로 바꿔줌.

노드 삭제

1. 삭제할 노드의 앞 노드를 삭제할 노드의 뒤 노드와 연결

2. 삭제할 노드의 연결 끊기(이건 선택)

Free list

힙의 빈공간을 모아두는 free list인가??

삭제한 노드들을 모아놓는다. 자바로 할 때는 없었는데 C로 해서 메모리 관리떄문에 필요한가?

삭제한 노드들을 Header와 가까운 쪽으로 차곡차곡 모아놓는다.

• 노드할당: FreeList의 첫번째 노드 제거. 리스트에 그 노드 추가. getNode()

• 노드제거: 리스트에서 노드 제거. Freelist의 첫번째 노드로 추가. returnNode(old)

시간없어서 생략. 추후 보강.

노드 탐색

시간 없어서 생략. 추후 보강.

---

노드 삽입/삭제/ 탐색/ 순서바꾸기(swap)/ 리스트 전체 메모리 해제(free), 내용 치환, *항상 free해주는것 잊지 않기

코드

  
  // C
  ​
  typedef struct _node
  {
      char *data;
      _node *next;
  }node;
  ​
  typedef struct _linkedList
  {
      //그냥 header가 어딘지 포인팅해주기 (노드 시작이 어딘지)
      node *header;
      node *trailer;
      
      //header라는 노드 생성해서 그 노드도 리스트로 포함해주기(java에서 썼던 방법)
      //node header;
      
  }linkedList;
  ​
  void addNode(linkedList *L, char *x)
  {
      node *newNode;
      node *p;
      newNode = (node *)malloc(sizeof(node));
  }
  ​
  ​

노드 각각에 대한건 _node 구조체라고 생각하면 된다. 각 node안에 무엇을 넣을 것인지 내용물을 설정하는것.

이 노드가 가질 data는 뭐고, 키값은 뭐고, 이 노드의 다음 노드는 뭐고... 이런것들.

그리고 리스트에 대한건 linkedList 구조체다. 이 연결리스트 안에 어떤 노드들이 연결되어있는지, 어떻게 연결되는지에 대해 정한다. 노드를 엮는 방법이 여기 있다는 뜻이다.

java로 배울 땐 그냥 Node header, trailer를 만들어서 연결했었다. C에서는 node *를 썼다. 이건 포인터 선언만 해 준 것이고, 나중에 malloc으로 메모리 할당을 해 주어야 한다. C에서도 똑같다. 다만 포인터 선언과 메모리 할당으로 쪼개진 것 뿐이지. Node로 할당한게 아니고 Node * + malloc으로 heap영역에 할당해주는 것 뿐이다.

그런데 왜 addNode같은 함수에서 (linkedList *L)을 쓰고, node *newNode일까? linkedList L, node newNode가 아니라 포인터를 쓰는 이유(linkedList *L, node *newNode)가 뭘까??

→ 정적할당 (node newNode)를 하게 되면 스택부분에 변수가 저장된다. 그러면 함수가 끝난 후 날아가버릴 수 있다. 하지만 동적할당(malloc)을 하게 되면 힙 부분에 메모리 공간이 할당된다. 이 부분은 사용자가 할당하고 해제할 수 있는 공간이므로, 임의로 덧씌워지지 않는다. 그래서 함수가 끝나고도 데이터를 보존시킬 수 있다.

힙과 스택 영역의 차이

단방향 연결 리스트

근데 자바에서는 왜 정적할당처럼 보였던 것일까? 사실 아니었던 거다.

Node newNode = new Node(); → 이 new라는 명령어가 힙 영역에 할당시키는 명령어였다!! 자바도 동적할당을 했던 거다!!

  
  // java로 배웠던 방법
  ​
  class Node
  {
      String data;
      Node next;
  }
  ​
  ​
  class LinkedList
  {
      Node header = new Node();
      Node trailer = new Node();
      header.data = null;
      trailer.data = null;
      
      header.next = trailer;
      
      
      void addNode(LinkedList L, String data)
      {
          Node newNode = new Node();
          newNode.next = header.next;
          newNode.data = data;
          header.next = newNode;
          
      }
  ​
  }