1.接口定义同顺序表的接口定义
1 package com.neusoft.List; 2 3 /** 4 * @author SimonsZhao 5 * 线性表的基本操作 6 *1.线性表置空 7 *2.线性表判空 8 *3.求线性表长度 9 *4.得到第i个元素的值10 *5.线性表第i个元素之前插入一个元素11 *6.删除并返回线性表中的第i个元素12 *7.线性表中首次出现指定数据元素的位置序号13 *8.输出线性表中的元素14 */15 public interface IList {16 //1.线性表置空17 public void clear();18 //2.线性表判空19 public boolean isEmpty();20 //3.求线性表长度21 public int length();22 //4.得到第i个元素的值23 public Object get(int i);24 //5.线性表第i个元素之前插入一个元素25 public void insert(int i,Object x);26 //6.删除并返回线性表中的第i个元素27 public void remove(int i);28 //7.线性表中首次出现指定数据元素的位置序号29 public int indexOf(Object x);30 //8.输出线性表中的元素31 public void display();32 33 } 2.定义存放数据域和指针域的节点信息
1 package com.neusoft.link; 2 3 public class Node { 4 public Object data;// 数据域 5 public Node next;// 指针域 6 public Node() { //构造空节点 7 this(null,null); 8 } 9 public Node(Object data){ //构造有一个参数的数据域10 this(data,null);11 }12 public Node(Object data,Node node){ //构造数据域和指针域13 this.data=data;14 this.next=node;15 }16 } 3.实现接口的所有方法
1 package com.neusoft.link; 2 3 import java.util.Scanner; 4 5 import com.neusoft.List.IList; 6 public class LinkedList implements IList { 7 public Node head;//链表的头指针 8 public LinkedList() { 9 head = new Node();//初始化头结点 10 } 11 public LinkedList(int n,boolean order){ 12 //如果order=1采用尾插法，如果order=2采用头插法 13 this(); 14 if (order) { 15 create1(n); 16 }else { 17 create2(n); 18 } 19 } 20 private void create1(int n) { 21 //尾插法 22 Scanner sc = new Scanner(System.in); 23 for (int i = 0; i < n; i++) { 24 insert(length(), sc.next()); 25 } 26 } 27 private void create2(int n) { 28 //头插法 29 Scanner sc = new Scanner(System.in); 30 for (int i = 0; i < n; i++) { 31 insert(0, sc.next()); 32 } 33 } 34 35 @Override 36 public void clear() { 37 //置空 38 head.data=null; 39 head.next=null; 40 } 41 42 @Override 43 public boolean isEmpty() { 44 // 判空 45 return head.next==null; 46 } 47 @Override 48 public int length() { 49 // 链表的长度 50 Node p = head.next; 51 int length=0; 52 while (p!=null) { 53 p=p.next; //指向后继节点 54 length++; 55 } 56 return length; 57 } 58 59 @Override 60 public Object get(int i) { 61 // 读取链表中第i个节点 62 Node p = head.next; 63 int j=0; 64 if (j>i||p==null) { 65 System.out.println("第"+i+"个元素不存在"); 66 } 67 while (p!=null&&j i-1||p==null) { 84 System.out.println("插入位置不合法"); 85 } 86 Node s = new Node(x);//新开辟的s节点 87 if (i==0) { //从头结点进行插入 88 s.next=head; 89 head=s; 90 }else { //从链表中间或表尾进行插入 91 s.next=p.next; 92 p.next=s; 93 } 94 95 } 96 97 @Override 98 public void remove(int i) { 99 // 删除单链表的第i个节点100 Node p = head;101 int j=-1;102 while (p.next!=null&&j i-1||p.next==null) {107 System.out.println("删除位置不合法");108 }109 p.next=p.next.next;110 }111 112 @Override113 public int indexOf(Object x) {114 // 查找值为x的位置115 Node p = head.next;116 int j=0;117 while (p!=null&&!p.data.equals(x)) {118 p= p.next;119 j++;120 }121 if (p!=null) {122 return j;123 }else {124 return -1;125 }126 }127 128 @Override129 public void display() {130 // 输出单链表的所有节点131 Node node = head.next;132 while(node !=null){133 System.err.println(node.data+" ");134 node=node.next;135 }136 }137 138 } 4.测试代码及结果分析
（输出指定位置元素的直接前驱和后继）
1 package com.neusoft.link; 2 3 import java.util.Scanner; 4 5 public class LinkedListTest { 6 public static void main(String[] args) { 7 int n=10; 8 LinkedList L= new LinkedList(); 9 for (int i = 0; i < n; i++) {10 L.insert(i, i);11 }12 System.out.println("请输入i的值：");13 Scanner sc = new Scanner(System.in);14 int nextInt = sc.nextInt();15 if (nextInt>0&&nextInt<=n) {16 System.out.println("第"+nextInt+"个元素的前驱是："17 +L.get(nextInt-1));18 }else {19 System.out.println("第"+nextInt+"个元素的前驱不存在");20 }21 }22 } 结果分析
5.补充代码---输出链表的后继节点
1 package com.neusoft.link; 2 3 import java.util.Scanner; 4 5 public class LinkedListTest { 6 public static void main(String[] args) { 7 int n=10; 8 LinkedList L= new LinkedList(); 9 for (int i = 0; i < n; i++) {10 L.insert(i, i);11 }12 System.out.println("请输入i的值：");13 Scanner sc = new Scanner(System.in);14 int nextInt = sc.nextInt();15 if (nextInt>0&&nextInt<=n) {16 System.out.println("第"+nextInt+"个元素的前驱是："17 +L.get(nextInt-1));18 }else {19 System.out.println("第"+nextInt+"个元素的前驱不存在");20 }21 22 if (nextInt>=0&&nextInt 显示结果：
END~