以前从来都是用C C++来写一些算法,数据结构
第一次用java写感觉十分的不亲切,不过相比于前两种语言来说,在没有指针的情况下,用java写感觉还是十分的简单。
先上一部分图解,以便于没有基础的小白理解以下
图解
个人觉得链表的插入删除并没有必要刻意去记,在理解的情况下写链表,链表并没有那么可怕。不过一次性写成功,本人还是比较开心dadadaa.
这里我用了一个 createLinkedList(E data) 方法,初始化链表。
暂时还没有想到不增加头节点的前提下,有好的方式来省略初始化。
话不多说,上代码
功能
- 定义节点
- 创建链表并初始化
- 头插法(把元素插到第一位)
- 尾插法(把元素插到最后一位)
- 删除结点
- 获取指定位置前驱结点
- 获取指定位置后继结点
- 获取链表长度
- 判空
10.遍历链表
代码
package LinkedList;
public class LinkedList<E> {
public class Node<E>{ //结点定义
public Node<E> next;
public Node<E> prve;
public E data;
public Node(E data) {
this.data = data;
this.next = null;
this.prve = null;
}
}
private Node<E> first; //头指针
private Node<E> last; //尾指针
private int length;
public void createLinkedList(E data) { //创建链表的初始化工作
Node<E> newNode = new Node<>(data);
newNode.prve = newNode;
newNode.next = newNode;
first = newNode;
last = newNode;
length++;
}
public void addFirst(E data) { //前插,头指针指向新节点
Node<E> newNode = new Node<>(data);
newNode.prve = last;
last.next = newNode;
newNode.next = first;
first.prve = newNode;
first = newNode;
length++;
}
public void addLast(E data) { //尾插,尾指针指向新节点
Node<E> newNode = new Node<>(data);
newNode.prve = last;
last.next = newNode;
newNode.next = first;
first.prve = newNode;
last = newNode; //尾指针继续指向尾部结点
length++;
}
public void del(E data) {
Node<E> p = first;
while(p.data != data) {
p = p.next;
}
/*
这里还要判断被删除的指针是不是 头指针或者 尾指针
(如果删除的是头指针,就指向当前位置后一位后一位。
如果删除的是 尾指针,就指向当前位置的前一位)
*/
if (p == first) {
first = p.next;
}else if(p == last) {
p = last.prve;
}
p.next.prve = p.prve;
p.prve.next = p.next;
length--;
}
public int length() { //链表长度
return length;
}
public E getIndexElePrve(int Index) { //指定位置的前驱结点
Node<E> p = first;
for(int i = 1;i<= Index;i++) {
p = p.next;
}
return p.prve.data;
}
public E getIndexEleNext(int Index) { //指定位置的后继结点
Node<E> p = first;
for(int i = 1;i<= Index;i++) {
p = p.next;
}
return p.next.data;
}
public boolean isEmpty() { //判空
if (length==0) {
return true;
}
return false;
}
public void show() {
Node<E> p = first;
/*
因为没有头节点,所以打印的时候稍显麻烦
如果按照正常的判断打印,就会少打印一个元素
所以我使用这种方式。
*/
System.out.println(p.data);
p = p.next;
while(p != first) {
System.out.println(p.data);
p = p.next;
}
}
}
实习生dc
发布了20 篇原创文章 · 获赞 1 · 访问量 463
私信
关注