上节分析了顺序表,这次我们分析一下链表,并简单手写一个单链表.
顺序表的特征上一节已经讲过:尾插效率高,支持随机访问;中间插入或删除效率低.
那么链式表又是怎样一种结构呢?他的存储又是怎么样的?
如果说顺序表是一个萝卜一个坑,那么链式表整体的结构就像一条链子.
如图所示:
image.png
在链表中,每一个元素都被看做是一个节点,他的数据结构底层是个Object 有一个属性next指向下一个元素,另一个属性用于存储数据.
知道了链表的数据结构,我们就来实现一下简单的单链表,包括常用的以下几个方法:
1. add系列方法
2. remove系列方法
3. get系列方法
4. Set方法
5. 转置方法
首先,按照数据结构,创建一个静态内部类 Node<E>,包含两个属性,E 和 Node<E>.其中E表示数据类型,Node<E>表示下一个节点.
private static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
Add系列方法:
add(E e)向末尾添加元素:
public void add(E e) {
if (head == null) {
//首次添加
head = new Node(e);
head.next = null;
size++;
} else {
Node node = head;
Node<E> node1 = new Node<>(e);
while (node.next != null) {
node = node.next;
}
node.next = node1;
size++;
}
}
add(int location,E e)向指定位置添加元素:
public void add(int location, E e) {
if (location > size) {
throw new IndexOutOfBoundsException("index out of bounds");
}
Node node1 = new Node(e);
if (location == 0) {
node1.next = head;
head = node1;
} else {
int now = 0;
Node node = head;
while (now != location-1) {
now++;
node = node.next;
}
Node node2 = node.next;
node.next = node1;
node1.next = node2;
}
size++;
}
remove方法:
E remove(int location),删除对应位置元素,并返回元素的值:
public E remove(int location) {
if (location < 0 || location >= size) {
throw new IndexOutOfBoundsException("index out if bounds");
}
size--;
if (location == 0) {
E item = head.item;
head = head.next;
return item;
} else {
Node<E> prev = head;
int now = 0;
while (now != location-1) {
prev = prev.next;
now++;
}
Node<E> next = prev.next;
Node<E> next1 = next.next;
prev.next = next1;
return next.item;
}
}
get方法:
E get(int location),获取对应位置节点的数据:
public E get(int location) {
if (location < 0 || location >= size) {
throw new IndexOutOfBoundsException("index out if bounds");
}
Node<E> e = head;
int now = 0;
while (now != location) {
e = e.next;
now++;
}
return e.item;
}
set方法:
set(int location, E e),修改对应位置的节点数据:
public void set(int location, E e) {
if (location < 0 || location >= size) {
throw new IndexOutOfBoundsException("index out if bounds");
}
int now = 0;
Node node = head;
while (now != location) {
node = node.next;
now++;
}
node.item = e;
}
转置:
1. 循环转置
public void reverse() {
if (size <=1) {
return;
}
Node prev = head;
Node curr = head.next;
Node temp;
while (curr != null) {
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head.next = null;
head = prev;
}
2. 递归转置
public void reverse2() {
if (size <=1) {
return;
}
reverse2(head);
}
public void reverse2(Node head) {
if(head==null||head.next==null) {
this.head=head;
return;
}
reverse2(head.next);
head.next.next=head;
head.next=null;
}
关于转置这块的解释,可以参见我的另一篇文章: 数据结构之List(一) 手写单链表
下节我们回顾一下栈和队列.
网友评论