什么是单链表IList接口代码实现
Node.class具体实现
linkedList.class 测试linkedListTest.class
什么是单链表相对与顺序表而言，链表的各元素只是逻辑上相邻，物理上并不相邻。所以无法做到随机访问，而只能顺序访问，但其插入和删除较为方便。
IList接口public interface IList {
//置空
public void clear();
//获取元素个数
public int length();
//判空
public boolean isEmpty();
//获取指定元素
public Object get(int i);
//新增元素
public void add(Object o);
//指定位置插入元素
public void insert(int index,Object o);
//移除元素
public void remove(int i);
//查找对应元素下标
public int indxeOf(Object o);
//输出所有元素
public void display();
}
代码实现
Node.class
节点类，其中包含一个数据和一个指向下一个节点的指针
public class Node {
public Object data;
public Node next;
public Node() {
this.data = null;
this.next = null;
}
public Node(Object data) {
this.data = data;
}
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"data= " + data +
'}';
}
}
具体实现
linkedList.class
public class linkedList implements IList {
public Node head;
public linkedList() {
this.head = new Node();
}
//置空
@Override
public void clear() {
head.data = null;
head.next = null;
}
//获取链表长度
@Override
public int length() {
Node p = head;
int len = 0;
while (p.next != null) {
p = p.next;
len++;
}
return len;
}
//带头结点的链表 判断首节点是否为空
@Override
public boolean isEmpty() {
return head.next == null;
}
//获取下标为i的元素
@Override
public Object get(int i) {
Node p = head.next;
int j = 0;
//不遍历整个链表
while (p != null && j < i) {
p = p.next;
j++;
}
//不存在或者表长为0
if(p == null || j > i) {
System.out.println("表长为0,或者第" + i +"位不存在。");
}
return p.data;
}
//使用尾插法
@Override
public void add(Object o) {
Node s = new Node(o);
Node p = head;
while (p.next != null) {
p = p.next;
}
p.next = s;
}
//头插法
public void addH(Object o) {
Node s = new Node(o);
s.next = head.next;
head.next = s;
}
//带头节点算法 不带头节点且插入位置为表头时，则需要替换表头节点
@Override
public void insert(int index, Object o) {
int j = -1;
Node p = head.next;
while (p != null && j < index-1) {
p = p.next;
j++;
}
if (j > index - 1 || p == null) {
System.out.println("插入位置不合法。");
}
Node present = new Node(o);
present.next = p.next;
p.next = present;
}
//移除下标为i的元素
@Override
public void remove(int i) {
Node p = head;//头节点开始
int j = -1;
while (p != null && j < i-1) {
p = p.next;
j++;
}
//i小于0或者达到链表末尾
if(j > i - 1 || p == null){
System.out.println("需要移除位置上没有元素。");
}
p.next = p.next.next;
}
//查找第一个o数据的下标
@Override
public int indxeOf(Object o) {
int j = 0;
Node p = head.next;
while (p != null && !p.data.equals(o)) {
p = p.next;
j++;
}
if(p == null)
return -1;
else
return j;
}
//输出
@Override
public void display() {
Node p = head.next;
while (p != null) {
System.out.println(p.toString());
p = p.next;
}
}
}
测试
linkedListTest.class
public class linkedListTest {
public static void main(String[] args) {
linkedList list = new linkedList();
System.out.println("尾插法测试");
list.add("零");
list.add("一");
list.add("二");
list.add("三");
list.add("四");
list.display();
System.out.println("============================= ");
System.out.println("判空测试");
if(list.isEmpty())
System.out.println("链表为空。");
else
System.out.println("链表不为空。");
System.out.println("============================= ");
System.out.println("length测试");
System.out.println("length: " + list.length());
System.out.println("============================= ");
System.out.println("移除测试");
list.remove(2);
list.display();
System.out.println("============================= ");
System.out.println("查找测试");
System.out.println("第下标为2的元素值为: " + list.get(2));
System.out.println("============================= ");
System.out.println("插入测试");
list.insert(1 , "二");
list.display();
System.out.println("============================= ");
System.out.println("定位测试");
System.out.println("零的位置是： " + list.indxeOf("零"));
System.out.println("四的位置是： " + list.indxeOf("四"));
System.out.println("============================= ");
System.out.println("置空测试");
list.clear();
System.out.println("清空后链表长度： " + list.length());
if(list.isEmpty())
System.out.println("链表为空。");
System.out.println("============================= ");
System.out.println("头插法测试");
list.addH("零");
list.addH("一");
list.addH("二");
list.addH("三");
list.addH("四");
list.display();
}
}
