黑马程序员技术交流社区

标题: 链表问题 [打印本页]
作者: 杨习平    时间: 2012-8-16 15:48
标题: 链表问题
单向链表是怎么样实现的，我个人就是不知道怎么回事，我从下手，高手将几个例子，具体说说，
作者: 周瑞    时间: 2012-8-16 16:05
JAVA实现单链表
（1）节点类
  1. public class Node {  
  2.   
  3.     private Object data;// 数据区  
  4.     private Node next; // 节点区  
  5.   
  6.     // 构造方法  
  7.     public Node(Object data, Node next) {  
  8.         this.data = data;  
  9.         this.next = next;  
  10.     }  
  11.   
  12.     public Object getData() {  
  13.         return data;  
  14.     }  
  15.   
  16.     public void setData(Object data) {  
  17.         this.data = data;  
  18.     }  
  19.   
  20.     public Node getNext() {  
  21.         return next;  
  22.     }  
  23.   
  24.     public void setNext(Node next) {  
  25.         this.next = next;  
  26.     }  
  27.   
  28. }  
复制代码
（2）链表类
  1. public class LinkedList {  
  2.   
  3.     private Node head; // 头结点  
  4.   
  5.     private int length; // 长度  
  6.   
  7.     // 构造方法  
  8.     public LinkedList() {  
  9.         head = new Node(null, null);  
  10.         length = 0;  
  11.     }  
  12.   
  13.     // 头插法（顺序相反）  
  14.     public void addHead(Object item) {  
  15.   
  16.         Node node = new Node(item, null);  
  17.   
  18.         node.setNext(head.getNext());  
  19.   
  20.         head.setNext(node);  
  21.   
  22.         length++;  
  23.     }  
  24.   
  25.     // 尾插法  
  26.     public void addTail(Object item) {  
  27.   
  28.         Node node = new Node(item, null);  
  29.         Node temp = head;  
  30.   
  31.         // 找到尾节点  
  32.         while (null != temp.getNext()) {  
  33.             temp = temp.getNext();  
  34.         }  
  35.   
  36.         temp.setNext(node);  
  37.   
  38.         length++;  
  39.     }  
  40.   
  41.     // 在指定位置添加节点  
  42.     public void addIndex(Object item, int index) {  
  43.   
  44.         Node node = new Node(item, null);  
  45.         Node temp = head;  
  46.   
  47.         // 找到要插入节点的前一个节点  
  48.         for (int i = 0; i < index - 1; i++) {  
  49.             temp = temp.getNext();  
  50.         }  
  51.   
  52.         node.setNext(temp.getNext());  
  53.   
  54.         temp.setNext(node);  
  55.   
  56.         length++;  
  57.   
  58.     }  
  59.   
  60.     // 查找指定位置的节点  
  61.     public void find(int index) {  
  62.   
  63.         if (index < 1 | index > length) {  
  64.             System.out.println("位置非法！");  
  65.         }  
  66.   
  67.         Node temp = head;  
  68.   
  69.         for (int i = 0; i < index; i++) {  
  70.             temp = temp.getNext();  
  71.         }  
  72.   
  73.         System.out.println("链表中第" + index + "节点的值是：" + temp.getData());  
  74.     }  
  75.   
  76.     // 删除  
  77.     public void delete(int index) {  
  78.   
  79.         if (index < 1 | index > 5) {  
  80.             System.out.println("位置非法！");  
  81.         }  
  82.   
  83.         Node temp = head;  
  84.   
  85.         // 找到要删除节点的前一个节点  
  86.         for (int i = 0; i < index - 1; i++) {  
  87.             temp = temp.getNext();  
  88.         }  
  89.   
  90.         length--;  
  91.   
  92.         temp.setNext(temp.getNext().getNext());  
  93.     }  
  94.   
  95.     // 打印链表  
  96.     public void prtn() {  
  97.   
  98.         Node temp = head.getNext(); // 指向第一个元素节点  
  99.   
  100.         while (null != temp) {  
  101.             System.out.print(temp.getData() + " ");  
  102.   
  103.             temp = temp.getNext();  
  104.         }  
  105.   
  106.         System.out.println("长度为" + length);  
  107.     }  
  108.   
  109.     public static void main(String[] args) {  
  110.   
  111.         // 测试  
  112.         LinkedList list = new LinkedList();  
  113.   
  114.         list.addHead(1);  
  115.         list.addHead(2);  
  116.         list.addHead(3);  
  117.         list.addHead(4);  
  118.   
  119.         System.out.print("采用头插法的链表是：");  
  120.         list.prtn();  
  121.         System.out.println();  
  122.   
  123.         System.out.print("添加一个节点：");  
  124.         list.addIndex("hello", 1);  
  125.         list.prtn();  
  126.         System.out.println();  
  127.   
  128.         System.out.print("查找节点：");  
  129.         list.find(1);  
  130.         System.out.println();  
  131.   
  132.         System.out.print("删除添加的节点");  
  133.         list.delete(1);  
  134.         list.prtn();  
  135.         System.out.println();  
  136.   
  137.         // 测试  
  138.         LinkedList list2 = new LinkedList();  
  139.   
  140.         list2.addTail(1);  
  141.         list2.addTail(2);  
  142.         list2.addTail(3);  
  143.         list2.addTail(4);  
  144.   
  145.         System.out.print("采用尾插法的链表是：");  
  146.         list2.prtn();  
  147.         System.out.println();  
  148.   
  149.         System.out.print("添加一个节点：");  
  150.         list2.addIndex("hello", 1);  
  151.         list2.prtn();  
  152.         System.out.println();  
  153.   
  154.         System.out.print("查找节点：");  
  155.         list2.find(1);  
  156.         System.out.println();  
  157.   
  158.         System.out.print("删除添加的节点");  
  159.         list2.delete(1);  
  160.         list2.prtn();  
  161.     }  
  162. }  
复制代码
（3）测试结果
采用头插法的链表是：4 3 2 1 长度为4

添加一个节点：hello 4 3 2 1 长度为5

查找节点：链表中第1节点的值是：hello

删除添加的节点4 3 2 1 长度为4

采用尾插法的链表是：1 2 3 4 长度为4

添加一个节点：hello 1 2 3 4 长度为5

查找节点：链表中第1节点的值是：hello

删除添加的节点1 2 3 4 长度为4



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2