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;
}
}