java 연결리스트 만들기(java linked list)

 

 

연결리스트란 자료가 링크로 연결되어 있는 구조를 말한다. 
말 다 필요없고 그림으로 보면 간단하다.

 

 

 

 

 

 

 

이렇게 되어 있는 것이 연결리스트이다.

 

예시로 설명하면 노드는 이름과, 다음번지 값을 가지고 있다.
10번지 노드는 이름이 김, 다음번지(20)의 값
20번지 노드는 이름이 이, 다음번지(30)의 값
30번지 노드는 이름이 박, 다음번지(40)의 값
40번지 노드는 이름이 홍, 다음번지(null)의 값

이다. 40번지 값이 가장 최근에 들어온 값으로 했다
(새로운 노드를 start 지점에 두는 방법도 있지만 본인은 이런식으로 구현했다)

기본적으로 자바에선 LinkedList를 클래스로 제공해주지만 직접 소스로 구현해보면 객체지향, 자료구조 등의 측면에서 많은 도움이 된다.

cur은 값이 추가될 때마다 맨 끝 노드를 참조하는 참조변수이다. 그림에는 그려지지 않았지만 지금 40번지를 가리키고 있을 것이다.

cur의 또 다른 용도는 값을 찾을 때 사용한다. start는 시작 지점이라서 움직이지 않고 대신 cur를 이용해서 움직인다.
cur = start를 하면 cur이 가장 첫 노드를 가리키게 될 것이다. 그리고 while문을 돌면 cur로 계속 이동할 수 있을 것이다.

본인이 만든 연결리스트는 아래 소스와 같다. 미리 말하지만 좋은 코드는 아니다. 그리고 완전히 만든 소스도 아니다(삽입, 정렬 같은 기능은 없다).
소스 수정은 추후 올리겠다~

대략적인 방법론은 밑 소스와 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

import java.util.Scanner;   class MyLinkedList{          Scanner in = new Scanner(System.in);          Node start = null;   //시작점을 갖는 참조변수     Node cur = null;    //맨 끝으로 이동하는 참조변수          class Node{         String name;         Node next = null;     }          public void add(String str)     {         /*          1. Node 객체를 만든다.          2. start가 null인가?          3. cur에 start 값을 대입한다.          4. cur.next가 null인가?          4-1. cur에 null이 아니면 cur에 cur.next 값 대입하고 다시 반복 -> 끝에 새로만든 노드 만듬          */         Node newNode = new Node();         newNode.name = str;         if(start == null)  //시작이 null이면         {             start = newNode;             return;   //만들고 빠져나감         }                  cur = start;  //null이 아니면         while(cur.next != null)         {             cur = cur.next;         }         cur.next = newNode;         //System.out.println(cur.name+" 뒤에 노드 추가!");     }          public void output()     {         if(start == null)    //만들어진 것이 없으면         {             System.out.println("생성된 연결리스트가 없습니다.");             return;         }                  cur = start;   //만들어진 것이 있으면 start(맨 처음을 가리키는) 애를 cur에 넘겨주어서         while(cur.next != null)         {             System.out.println("이름 ! : "+cur.name);             cur = cur.next;         }         if(cur.next == null)             System.out.println("이름 ! : "+cur.name);     }          public void delete()     {         if(start == null)  //아예 값이 없으면         {             System.out.println("삭제할 값이 없습니다.");             return;         }                  System.out.println("찾을 이름을 입력하세요: ");         String name = in.next();                  if(start.name.equals(name))         {             //맨 처음에 찾았을 때.             System.out.println(start.name+" 찾았습니다.");             start  = start.next;             return;         }                  cur = start;         while(cur.next != null)  //맨처음에 값이 없어서 리스트 목록에서 찾을때         {             if(name.equals(cur.next.name))             {                 System.out.println(cur.next.name+" 찾았습니다.");                 cur.next = cur.next.next;                 return;             }                          cur = cur.next;         }                  System.out.println("찾는 값이 없습니다.");                } }   public class Study_6_08_2 {       public static void main(String[] args) {         MyLinkedList list = new MyLinkedList();         list.add("홍길동");         list.add("김길동");         list.add("박길동");         list.add("이길동");         list.add("이순신");         list.add("강감찬");         list.add("이소룡");                           list.output();                  list.delete();                  list.output();     }   }   Colored by Color Scripter

cs