数据结构-双链表(java)
2020-05-11 本文已影响0人
鼬殿
简介:
双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱
链表的设计
代码实现
package com.njf;
public class DoublyLinkedList<E> {
/**
* 链表大小
*/
private int size;
/**
* 指向头结点的引用
*/
private Node<E> first;
/**
* 指向尾结点的引用
*/
private Node<E> last;
private static final int ELEMENT_NOT_FOUND = -1;
private static class Node<E> {//创建节点
//数据域
E element;
//指向前结点的引用
Node<E> prev;
//指向后继结点的引用
Node<E> next;
public Node(Node<E> prev,E element, Node<E> next) {//构造函数
this.prev = prev;
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
/**
* 获取index位置对应的节点对象
*/
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size>>1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
/**
* 清除所有链表数据
*/
public void clear() {
size = 0;
first = null;
last = null;
}
/**
* 链表大小
* @return
*/
public int size() {
return size;
}
/**
* 链表是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个数据元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加节点到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
/**
* 获取index位置的节点中的数据
* @param index
* @return
*/
public E get(int index) {
return node(index).element;
}
/**
* 设置index位置节点中的数据
* @param index
* @param element
* @return 原来的节点中的数据
*/
public E set(int index, E element) {
//获取当前节点
Node<E> node = node(index);
E oldElement = node.element;
node.element = element;
return oldElement;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
if (index == size) {
Node<E> oldLast = last;
last = new Node<>(last, element, null);
if (oldLast == null) {
first = last;
}else {
oldLast.next = last;
}
}else {
//获取当前节点
Node<E> next = node(index);
//获取前一个节点
Node<E> prev = next.prev;
Node<E> node = new Node<> (prev,element,next);
next.prev = node;
if (prev == null) {//index == 0
first = node;
}else {
prev.next = node;
}
}
size ++;
}
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index) {
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) {
first = next;
}else {
prev.next = next;
}
if (next == null) {
last = prev;
}else {
next.prev = prev;
}
size--;
return node.element;
}
/**
* 查看某个节点元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
}else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element.equals(element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
根据上面双链表的调用验证结果如下
size=4, [null_11_66, 11_66_33, 66_33_44, 33_44_null]
双向循环链表(java)
链表的设计
代码实现
package com.njf;
public class DoublyCycleLinkedList<E> {
/**
* 链表大小
*/
private int size;
/**
* 指向头结点的引用
*/
private Node<E> first;
/**
* 指向尾结点的引用
*/
private Node<E> last;
/**
* 指向当前节点的引用
*/
private Node<E> current;
private static final int ELEMENT_NOT_FOUND = -1;
private static class Node<E> {//创建节点
//数据域
E element;
//指向前结点的引用
Node<E> prev;
//指向后继结点的引用
Node<E> next;
public Node(Node<E> prev,E element, Node<E> next) {//构造函数
this.prev = prev;
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
/**
* 获取index位置对应的节点对象
*/
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size>>1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
/**
* 指向第一个节点
*/
public void reset() {
current = first;
}
/**
* 返回当前节点指向的下一个节点的元素
*/
public E next() {
if (current == null) return null;
current = current.next;
return current.element;
}
/**
* 清除所有链表数据
*/
public void clear() {
size = 0;
first = null;
last = null;
}
/**
* 链表大小
* @return
*/
public int size() {
return size;
}
/**
* 链表是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个数据元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加节点到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
/**
* 获取index位置的节点中的数据
* @param index
* @return
*/
public E get(int index) {
return node(index).element;
}
/**
* 设置index位置节点中的数据
* @param index
* @param element
* @return 原来的节点中的数据
*/
public E set(int index, E element) {
//获取当前节点
Node<E> node = node(index);
E oldElement = node.element;
node.element = element;
return oldElement;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
if (index == size) {
Node<E> oldLast = last;
last = new Node<>(last, element, first);
if (oldLast == null) {
first = last;
first.prev = last;
last.next = first;
}else {
oldLast.next = last;
first.prev = last;
}
}else {
//获取当前节点
Node<E> next = node(index);
//获取前一个节点
Node<E> prev = next.prev;
Node<E> node = new Node<> (prev,element,next);
next.prev = node;
prev.next = node;
if (next == first) {//index == 0
first = node;
}
}
size ++;
}
public E remove() {
if (current == null) return null;
Node<E> next = current.next;
E element = remove(current);
if (size == 0) {
current = null;
}else {
current = next;
}
return element;
}
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index) {
return remove(node(index));
}
private E remove(Node<E> node) {
if (size == 1) {
first = null;
last = null;
}else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if (node == first) {
first = next;
}
if (node == last) {
last = prev;
}
}
size--;
return node.element;
}
/**
* 查看某个节点元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
}else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element.equals(element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
根据上面双链表的调用验证结果如下
size=4, [44_11_66, 11_66_33, 66_33_44, 33_44_11]
利用双向循环链表解决约瑟夫问题（Josephus Problem）
如下：
从第一个元素开始，每次第3个元素杀掉，直到全部杀死为止
用双向循环链表主要实现三个方法
1. 让 current 指向头结点 first
public void reset() {
current = first;
}
2. 让 current 往后走一步，也就是 current = current.next
public E next() {
if (current == null) return null;
current = current.next;
return current.element;
}
3. 删除 current 指向的节点，删除成功后让 current 指向下一个节点
public E remove() {
if (current == null) return null;
Node<E> next = current.next;
E element = remove(current);
if (size == 0) {
current = null;
}else {
current = next;;
}
return element;
}
下面是调用关系
package com.njf;
public class Main
static void josephus() {
DoublyCycleLinkedList<Integer> list = new DoublyCycleLinkedList<>();
for (int i = 1; i <= 8; i++) {
list.add(i);
}
list.reset();
while (!list.isEmpty()) {
list.next();
list.next();
System.out.println(list.remove());
}
}
public static void main(String[] args) {
josephus();
}
每次删除的元素如下：
3
6
1
5
2
8
4
7
