1.연결리스트는 연결자료구조 방식이다.
(자료구조에서 데이터를 구조화 시키는 기본 표현 방식에는 순차 자료 구조 방식과 연결자료 구조 방식이 있다.)
2.연결리스트는 순차 선형리스트인 배열과는 달리 삽입 삭제 이동에 있어서 오버헤드가 적다.
h3.단순연결리스트
연결리스트는 노도단위구조로 구분 되어진다.
단순 연결리스트에서 노드의 추가 삭제 등의 처리를 구현한 코드이다.
작업순서
-1.노드 생성 (노드란 주소와 데이터의 결합 주소는 C에서는 포인터가 되겠다)
-2.노드삽입 메소드 구현
--2.1 첫번째리스트에 노드 삽입
--2.2 중간리스트에 노드 삽입
--2.3 마지막리스트에 노드 삽입
-3.노드삭제 메소드 구현
-4.노드검색 메소드 구현
노드생성
public class ListNode {
private String data;
private ListNode link = null;
public ListNode() {
// TODO Auto-generated constructor stub
this.data = null;
this.link = null;
}
public ListNode(String data, ListNode node) {
// TODO Auto-generated constructor stub
this.data = data;
this.link = node;
}
public ListNode(String data) {
// TODO Auto-generated constructor stub
this.data = data;
}
public String getData() {
return this.data;
}
}
메소드 구현
public class LinkedList {
private ListNode head = null;
public LinkedList() {
// TODO Auto-generated constructor stub
this.head = null;
}
public void insertFirstNode(String data){
ListNode newNode = new ListNode(data);
if (this.head == null) {
this.head = newNode;
}
else{
ListNode tmpListNode = head;
this.head = newNode;
newNode.link = tmpListNode;
}
}
public void insertMiddleNode(ListNode pre, String data){
ListNode newNode = new ListNode(data);
newNode.link = pre.link;
pre.link = newNode;
}
public void insertLastNode(String data){
ListNode newNode = new ListNode(data);
if(head == null){
this.head = newNode;
}
else{
ListNode temp = head;
while(temp.link != null) temp = temp.link;
temp.link = newNode;
}
}
public void deleteLastNode(){
ListNode pre, temp;
if(head == null) return;
if(head.link == null){
head = null;
}
else{
pre = head;
temp = head.link;
while(temp.link != null){
pre = temp;
temp = temp.link;
}
pre.link = null;
}
}
public ListNode searchNode(String data){
ListNode temp = this.head;
while(temp != null){
if(data == temp.getData())
return temp;
else temp = temp.link;
}
return temp;
}
public void reverseList(){
ListNode next = head;
ListNode current = null;
ListNode pre = null;
while(next != null){
pre = current;
current = next;
next = next.link;
current.link = pre;
}
head = current;
}
public void printList(){
ListNode temp = this.head;
System.out.printf("L = (");
while(temp != null){
System.out.printf(temp.getData());
temp = temp.link;
if(temp != null){
System.out.printf(", ");
}
}
System.out.println(")");
}
}
실행코드
public class LinkedListMain {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList L = new LinkedList();
System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
L.insertLastNode("화");
L.insertLastNode("수");
L.insertLastNode("금");
L.printList();
System.out.println("(2) 맨앞에 월 노드 삽입하기");
L.insertFirstNode("월");
L.printList();
System.out.println("(2) 토 노드를 찾고 수 노드 뒤에 목 노드 삽입하기");
ListNode pre = L.searchNode("토");
if(pre == null)
System.out.println("검색실패>> 찾는 데이터가 없습니다.");
pre = L.searchNode("수");
L.insertMiddleNode(pre, "목");
L.printList();
System.out.println("(3) 리스트의 노드를 역순으로 바꾸기");
L.reverseList();
L.printList();
System.out.println("(4) 리스트의 마지막 노드 삭제하기");
L.deleteLastNode();
L.printList();
}
}
h3.환형(원형)연결리스트
환형(원형)연결리스트 노도단위구조로 구분 되어진다.
단순 연결리스트와 차이점은 가장 마지막 노드가 첫번째 노드를 가르키는 구조이다.
연결리스트는 검색시 이전 노드를 접근 하기 위해서는 첫번째 노드 부터 다시 접근해야 하지만
원형연결리스트는 단순연결리스트와는 다르게 검색할때 노드를 따라 검색을 하다보면 이전노드에 접근할수 있다.
구조는 단순연결리스트와 완전히 동일하지만 마지막 노드가 첫번째 노드를 가르킨다.
public class CLinkedList {
private ListNode head = null;
public CLinkedList() {
// TODO Auto-generated constructor stub
this.head = null;
}
public void insertFirstNode(String data){
ListNode newNode = new ListNode(data);
if (this.head == null) {
this.head = newNode;
this.head.link = head;
}
else{
ListNode temp = this.head;
while (temp.link != head) {
temp = temp.link;
}
newNode.link = temp.link;
this.head = newNode;
temp.link = newNode;
}
}
public void insertMiddleNode(ListNode pre, String data){
ListNode newNode = new ListNode(data);
newNode.link = pre.link;
pre.link = newNode;
}
public void insertLastNode(String data){
ListNode newNode = new ListNode(data);
if(head == null){
this.head = newNode;
this.head.link = head;
}
else{
ListNode temp = head;
while(temp.link != head) temp = temp.link;
temp.link = newNode;
newNode.link = head;
}
}
public void deleteLastNode(){
ListNode pre, temp;
if(head == null) return;
if(head.link == null){
head = null;
}
else{
pre = head;
temp = head.link;
while(temp.link != head){
pre = temp;
temp = temp.link;
}
pre.link = head;
}
}
public ListNode searchNode(String data){
ListNode temp = this.head;
while(temp.link != head && temp != null){
if(data == temp.getData())
return temp;
else temp = temp.link;
}
return temp;
}
public void printList(){
ListNode temp = this.head;
System.out.printf("L = (");
while(temp != null && temp.link != this.head){
System.out.printf(temp.getData());
temp = temp.link;
if(temp != null && temp.link != this.head){
System.out.printf(", ");
}
}
System.out.println(")");
}
}
public class CLinkedListMain {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CLinkedList L = new CLinkedList();
System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
L.insertLastNode("화");
L.insertLastNode("수");
L.insertLastNode("금");
L.printList();
System.out.println("(2) 맨앞에 월 노드 삽입하기");
L.insertFirstNode("월");
L.printList();
System.out.println("(2) 토 노드를 찾고 수 노드 뒤에 목 노드 삽입하기");
ListNode pre = L.searchNode("토");
if(pre == null)
System.out.println("검색실패>> 찾는 데이터가 없습니다.");
pre = L.searchNode("수");
L.insertMiddleNode(pre, "목");
L.printList();
System.out.println("(4) 리스트의 마지막 노드 삭제하기");
L.deleteLastNode();
L.printList();
}
}
h3.이중연결리스트
단순연결리스트에서 선행 노드에 접근 하기가 어렵다는 점을 개선해서 원형 연결리스트를 구성했지만 원형리스트도
바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제점이 있다. 이는 링크가 한방향으로만 되어 있어서
그렇기 때문 이므로 양쪽에 링크를 두는 구성 형식이 이중연결 리스트 이다.
public class DListNode {
private String data;
DListNode llink = null;
DListNode rlink = null;
public DListNode() {
// TODO Auto-generated constructor stub
this.data = null;
this.llink = null;
this.rlink = null;
}
public DListNode(String data, DListNode lnode, DListNode rnode) {
// TODO Auto-generated constructor stub
this.data = data;
this.llink = lnode;
this.rlink = rnode;
}
public DListNode(String data) {
// TODO Auto-generated constructor stub
this.data = data;
}
public String getData() {
return this.data;
}
}
public class DLinkedList {
DListNode head = null;
public DLinkedList() {
// TODO Auto-generated constructor stub
this.head = null;
}
public void insertFirstNode(String data){
DListNode newNode = new DListNode(data);
if (this.head == null) {
this.head = newNode;
}
else {
DListNode tmpNode = this.head;
newNode.rlink = tmpNode;
tmpNode.llink = newNode;
this.head = newNode;
}
}
public void insertLastNode(String data){
DListNode newNode = new DListNode(data);
if (this.head == null) {
this.head = newNode;
}
else {
DListNode tmpNode = this.head;
while (tmpNode.llink != null)
tmpNode = tmpNode.rlink;
tmpNode.rlink = newNode;
newNode.llink = tmpNode;
}
}
}