1.链表的概念
在计算机科学中,链表是数据元素的线性集合,其每个元素都指向下一个元素,元素储存上并不连续。
创建链表如图所示和相关代码
public class danlianbiao {
private Node head=null;//头部第一个结点
private static class Node{//后面的每个结点
int value;
Node next;
public Node(int value,Node next) {
this.value=value;
this.next=next;
}
}
//增加元素 头插法
public void addFirst(int value) {
//1.假设是空表 插入结点
head = new Node(value,null);
//2.假设非空表 插入结点
head = new Node(value,head);
}
}
//1.遍历元素 loop 1.while public void loop() { Node p=head; while(p!=null) { System.out.println("遍历元素:"+p.value); p=p.next; } } //2.遍历元素 loop2 2.while public void loop2() { Node p ; for(p=head;p!=null;p=p.next) { System.out.println("遍历元素:"+p.value); } } //3.遍历元素 public void loop3(Consumer<Integer> consumer) { Node p ; for(p=head;p!=null;p=p.next) { consumer.accept(p.value); } } //4.遍历元素 迭代器 @Override public Iterator iterator() { // TODO Auto-generated method stub return new Iterator<Integer>() { Node p=head; @Override public boolean hasNext() { // TODO Auto-generated method stub return p!=null; } @Override public Integer next() { // TODO Auto-generated method stub int v = p.value; p = p.next; return v; } }; }
上述代码就是遍历元素的方法
写个测试类进行检测:
package 单链表; public class testdanlianbiao { public static void main(String[] args) { danlianbiao d = new danlianbiao(); //头插法 添加元素 d.addFirst(0); d.addFirst(1); d.addFirst(2); d.addFirst(3); d.addFirst(4); //遍历元素 d.loop(); } }
结果显示
尾部插入法:
//尾部插入法 //首先找到最后一个元素 public Node findLast() { //head头部为空 if(head==null) { return null; } Node p; for(p=head;p.next!=null;p=p.next) { } return p; } //尾部插入 public void addLast(int value) { //判断链表是否为空 Node last = findLast(); if(last==null) { addFirst(value); return; } last.next = new Node(value,null); }
尾部插入法实验结果:
//首先获取那个结点并将其私有化 private Node findNode(int index) { Node node ; int i=0; for(node=head;node!=null;node=node.next,i++) { if(index==i) { return node; } } return null; } public int get(int index) { Node node=findNode(index); if(node==null) { throw new IllegalArgumentException("没有该下标 [%d]"+index); } return node.value; } //向索引位置添加元素 public void insert(int index,int value) { if(index==0) { addFirst(value); } Node prev=findNode(index-1); if(prev==null) { throw new IllegalArgumentException("没有该下标 [%d]"+index); } prev.next = new Node(value,prev.next); } //删除元素 第一个元素 public void removeFirst() { // Node firstNode = findNode(0); // head.next = firstNode.next; if(head==null) { throw new IllegalArgumentException("没有该下标 [%d]"+0); } head = head.next; } //删除其中元素不是第一个元素 public void remove(int index) { if(index==0) { // throw new IllegalArgumentException("没有该下标 [%d]"+0); removeFirst(); } Node prev = findNode(index-1); if(prev==null) { throw new IllegalArgumentException("没有该下标 [%d]"+0); } Node removed = prev.next; if(removed==null) { throw new IllegalArgumentException("没有该下标 [%d]"+0); } prev.next = removed.next; } }