简介:
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的，由一系列结点组成，每个结点除了要存储数据外，还需存储指向后继结点或前驱结点的存储地址。
动态数组有个明显的缺点,可能会造成内存空间的大量浪费,链表不需要提前分配存储空间，元素个数不受限制
链表的设计
单链表
java单链表的代码实现
package com.njf;
public class LinkedList<E> {//泛型
/**
* 链表大小
*/
private int size;
/**
* 指向头结点的引用
*/
private Node<E> first;
private static final int ELEMENT_NOT_FOUND = -1;
private static class Node<E> {//创建节点
//数据域
E element;
//指向后继结点的引用
Node<E> next;
public Node(E element, Node<E> next) {//构造函数
this.element = element;
this.next = next;
}
}
/**
* 根据索引返回一个节点
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 清除所有链表数据
*/
public void clear() {
size = 0;
first = 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 == 0) {
first = new Node<>(element, first);
}else {
//先获取前一个节点
Node<E> priviousNode = node(index-1);
priviousNode.next = new Node<>(element, priviousNode.next);
}
size ++;
}
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index) {
Node<E> node = first;
if (index == 0) {
first = first.next;
}else {
Node<E> previousNode = node(index - 1);
node = previousNode.next;
previousNode.next = previousNode.next.next;
}
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.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
swift单链表的实现
import UIKit
class LinkedList<E> where E:Equatable{
fileprivate var size : Int = 0
fileprivate var first : Node<E>?
fileprivate let ELEMENT_NOT_FOUND : Int = -1;
//定义内部节点
fileprivate class Node<E> where E:Equatable{
static func == (lhs: Node<E>, rhs: Node<E>) -> Bool {
return lhs.element == rhs.element
}
var element : E
var next : Node<E>?
init(element : E){//构造函数
self.element = element;
}
}
/**
* 根据索引返回一个节点
*/
fileprivate func node(index:Int) ->Node<E>{
//判断index
rangeCheck(index: index)
var node : Node<E> = first!
for _ in 0..<index{
if node.next != nil {
node = node.next!
}
}
return node
}
/**
* 清除所有链表数据
*/
public func clear(){
size = 0
first = nil
}
/**
* 链表大小
* @return
*/
public func linkSize()->Int{
return size
}
/**
* 链表是否为空
* @return
*/
public func isEmpty()->Bool{
return size == 0
}
/**
* 是否包含某个数据元素
* @param element
* @return
*/
public func contains(element:E) ->Bool{
return indexOf(element: element) != ELEMENT_NOT_FOUND
}
/**
* 添加节点到尾部
* @param element
*/
public func add(element : E){
add(index: size, element: element)
}
/**
* 获取index位置的节点中的数据
* @param index
* @return
*/
public func getElement(index:Int) ->E{
return node(index: index).element
}
/**
* 设置index位置节点中的数据
* @param index
* @param element
* @return 原来的节点中的数据
*/
public func setElement(index:Int,element:E) ->E{
//获取当前节点
let currentNode:Node<E> = node(index: index)
let oldElement:E = currentNode.element
currentNode.element = element
return oldElement
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public func add(index:Int,element:E){
if index == 0 {//头插法
let tempNode = Node(element: element)
tempNode.next = first
first = tempNode
}else{
//获取前一个节点
let previousNode:Node<E> = node(index: index - 1)
//当前节点
let currentNode = Node(element: element)
currentNode.next = previousNode.next
previousNode.next = currentNode
}
size+=1
}
/**
* 删除index位置的节点
* @param index
* @return
*/
public func remove(index:Int) ->E{
var currentNode : Node<E> = first!
if index == 0 {
first = first?.next
}else{
//获取前一个节点
let previousNode:Node<E> = node(index: index - 1)
currentNode = previousNode.next!
previousNode.next = previousNode.next!.next
}
size-=1
return currentNode.element
}
/**
* 查看某个节点元素的索引
* @param element
* @return
*/
public func indexOf(element:E) ->Int{
var initNode:Node<E> = first!
if element is NSNull{
for i in 0..<size{
if initNode.element is NSNull{
return I
}
initNode = initNode.next!
}
}else{
for i in 0..<size{
if initNode.element == element{
return I
}
initNode = initNode.next!
}
}
return ELEMENT_NOT_FOUND
}
public func display(){
var currentNode : Node<E> = first!
var printStr : String = "size="
printStr.append("\(size)")
printStr.append(", [")
for i in 0..<size{
if (i != 0) {
printStr.append(", ");
}
printStr.append("\(currentNode.element)")
if currentNode.next != nil{
currentNode = currentNode.next!
}
}
printStr.append("]");
print(printStr)
}
fileprivate func outOfBounds(index:Int) {
print("index = \(index) 越界了")
assert(false)
}
fileprivate func rangeCheck(index:Int){
if index<0 || index >= size{
outOfBounds(index: index)
}
}
fileprivate func rangeCheckForAdd(index:Int){
if index<0 || index > size{
outOfBounds(index: index)
}
}
}
下面是swift调用和显示结果
let list:LinkedList<Int> = LinkedList()
list.add(element: 50)
list.add(element: 30)
list.add(element: 20)
list.add(index: 1, element: 10)
list.display()
let index = list.indexOf(element: 30)
print(index)
let element = list.remove(index: 0)
print(element)
list.display()
size=4, [50, 10, 30, 20]
2
50
size=3, [10, 30, 20]
虚拟头结点
◼ 有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）
public LinkedList() {
first = new Node<>(null, null);
}
单向循环链表
java代码实现
package com.njf;
public class SingleCycleLinkedList<E> {
/**
* 链表大小
*/
private int size;
/**
* 指向头结点的引用
*/
private Node<E> first;
private static final int ELEMENT_NOT_FOUND = -1;
private static class Node<E> {//创建节点
//数据域
E element;
//指向后继结点的引用
Node<E> next;
public Node(E element, Node<E> next) {//构造函数
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(element).append("_").append(next.element);
return sb.toString();
}
}
/**
* 根据索引返回一个节点
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 清除所有链表数据
*/
public void clear() {
size = 0;
first = 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 == 0) {
Node<E> newFirst = new Node<>(element, first);
Node<E> last = (size == 0) ? newFirst : node(size - 1);
last.next = newFirst;
first = newFirst;
}else {
//先获取前一个节点
Node<E> priviousNode = node(index-1);
priviousNode.next = new Node<>(element, priviousNode.next);
}
size ++;
}
/**
* 删除index位置的节点
* @param index
* @return
*/
public E remove(int index) {
Node<E> node = first;
if (index == 0) {
if (size == 1) {
first = null;
}else {
Node<E> last = node(size - 1);
first = first.next;
last.next = first;
}
}else {
Node<E> previousNode = node(index - 1);
node = previousNode.next;
previousNode.next = previousNode.next.next;
}
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();
}
}
下面是调用和显示结果
package com.njf;
public class Main {
static void testList(SingleCycleLinkedList<Integer> list) {
list.add(11);
list.add(22);
list.add(33);
list.add(44);
list.add(0, 55); // [55, 11, 22, 33, 44]
list.add(2, 66); // [55, 11, 66, 22, 33, 44]
list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]
list.remove(0); // [11, 66, 22, 33, 44, 77]
list.remove(2); // [11, 66, 33, 44, 77]
list.remove(list.size() - 1); // [11, 66, 33, 44]
Asserts.test(list.indexOf(44) == 3);
Asserts.test(list.contains(33));
Asserts.test(list.get(0) == 11);
Asserts.test(list.get(1) == 66);
Asserts.test(list.get(list.size() - 1) == 44);
System.out.println(list);
}
public static void main(String[] args) {
testList(new SingleCycleLinkedList<>());
}
}
size=4, [11_66, 66_33, 33_44, 44_11]
网友评论